二叉树的遍历

  二叉树的遍历可以分为：前序遍历，中序遍历，后序遍历。这里的序我们可以记为父节点所在的顺序。
则打印顺序为：

• 前序遍历：父->左子->右子；
• 中序遍历：左子->父->右子；
• 后序遍历：左子->右子->父;
  注意点：如果该二叉树为二叉搜索树，中序遍历的结果，是递增有序的序列。
  例如：
  
  节点定义：

 //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> traversal(TreeNode root) {
   
        List<Integer> result = new ArrayList();
        if(root==null){
   
            return result;
        }
        List<Integer> left =  traversal(root.left);
        List<Integer> right = traversal(root.right);
        /*1. 前序遍历*/
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);
        /*2. 中序遍历 result.addAll(left); result.add(root.val); result.addAll(right); */
		/*3. 后序遍历 result.addAll(left); result.addAll(right); result.add(root.val); */
        return result;
    }
}

前序遍历：使用栈

步骤：

1. 将root压入栈内
2. 栈弹出节点，将弹出节点的右节点-左节点压入栈内。
3. 回到第2步，最终完成树的遍历
   图解：
   
   代码实现：

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;
    }
}

中序遍历：栈实现

class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
   
        List<Integer> result = new ArrayList();
        if(root==null){
   
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode current = root;
        while(current!=null||!stack.isEmpty()){
   
            while(current!=null){
   
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
}

后序遍历：栈实现

class Solution {
   
    public List<Integer> postorderTraversal(TreeNode root) {
   
        List<Integer> result = new ArrayList();
        if(root==null){
   
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode current = root;
        while(current!=null||!stack.isEmpty()){
   
            while(current!=null){
   
                stack.push(current);
                current = current.left;
            }
            TreeNode node = stack.peek();
            if(node.right==null){
   
                node = stack.pop();
                result.add(node.val);
            }
            current = node.right;
            node.right = null;
        }
        return result;
    }
}

如有错误，大家可以批评指正。