二叉树的遍历（前序、中序、后序）Java详解与代码实现

递归遍历

前序，中序，后序

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*///前序遍历
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();preorder(root,res);return res;}void preorder(TreeNode root, List<Integer> res){if(root==null){return;}res.add(root.val);preorder(root.left,res);preorder(root.right,res);}
}
//中序遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();inorder(root,res);return res;}void inorder(TreeNode root,List<Integer> res){if(root==null){return;}inorder(root.left,res);res.add(root.val);inorder(root.right,res);}
}
//后序遍历
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();postOrder(root,res);return res;}void postOrder(TreeNode root,List<Integer> res){if(root==null){return;}postOrder(root.left,res);postOrder(root.right,res);res.add(root.val);}
}

这三个遍历，理解起来都是差不多的

以前序遍历为例

以每一个树或子树的根节点和List集合作为函数的参数返回值类型是void.

如果碰到每一个树或子树的根节点是空，就结束递归，结束函数

否则，先把根节点的值收入集合，再把左右结点(子树)的值收入集合

最后调用函数之后，返回这个集合

迭代法（非递归）

前序，后序

前序

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result=new ArrayList<>();if (root==null){return result;}Stack<TreeNode> stack=new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node=stack.pop();result.add(node.val);if (node.right!=null){stack.push(node.right);}if (node.left!=null){stack.push(node.left);}}return result;}
}

用栈模拟(实现)递归

先把树或某一子树的根节点入栈，然后，进入数组

再分别把右左子树的根节点入栈，然后分别将二者进入数组（右先入栈左后入栈，才能保证左先入数组，右后入数组）

这样左中右结点进入数组的顺序为：中左右

后序

以此类推，入栈的顺序为中左右，这样入数组的顺序为中右左，然后再将数组逆序对调

这样，数组输出的顺序就是左右中

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result=new ArrayList<>();if (root==null){return result;}Stack<TreeNode> stack=new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode node=stack.pop();result.add(node.val);if (node.left!=null){stack.push(node.left);}if (node.right!=null){stack.push(node.right);}}Collections.reverse(result);return result;}
}

要注意的是，Java中，List没有将集合元素逆序对调的方法，所以，要使用Collections的reverse方法

中序

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();if (root==null){return res;}Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){if (cur!=null){stack.push(cur);cur=cur.left;}else{//就是，cur为空的时候cur=stack.pop();//出栈，并让cur指向他res.add(cur.val);//这里是处理中间结点cur=cur.right;//既然没有左子节点，那就看看有没有右子节点}}return res;}
}

这里的遍历方式和前序后序不一样了

前序后序差不多算是遍历到哪个结点就处理哪个节点。这里不一样，这里是先处理左节点，左子树的左子树的左子树的左……左节点……所以，要先遍历到最左的左节点，然后再看最左节点的根节点然后他的根结点的右子节点。

这里还用到了一个指针来指向要处理的树的结点

二叉树迭代遍历法的统一写法风格

我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！ (opens new window)中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法

Java： 迭代法前序遍历代码如下:

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}

迭代法中序遍历代码如下:

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;
}
}

迭代法后序遍历代码如下:

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
}