二叉树遍历

通过递归方式遍历二叉树非常简单，只需要调整访问左子树、右子树、当前结点这三个语句的顺序，就可以实现三种遍历，但是毕竟需要递归调用，运算速度不及迭代方式、而且在面试中也会经常遇到，本问简单介绍几种迭代实现方式。

前序遍历（preorder）

1、 直接利用栈的FILO特性实现，后访问的先入栈

public void preorder(TreeNode root){        if(root == null)            return;        LinkedList
    
      stack = new LinkedList<>();        stack.push(root);        while(!stack.isEmpty()){            root = stack.pop();            visit(root);            if(root.right != null)                stack.push(root.right);            if(root.left != null)                stack.push(root.left);        }    }
    

每次先将右子树压栈，那么出栈时先访问左子树。

2、 dfs思想，优先向左子树访问,然后每次出栈后，再访问右子树

public void preorderTraversal(TreeNode root) {        LinkedList
    
      stack = new LinkedList<>();        while(root != null || !stack.isEmpty()){            while(root != null){                stack.push(root);                visit(root);                root = root.left;            }            root = stack.pop();            root = root.right;        }    }
    

中序遍历（inorder）

1、 和前面前序遍历dfs思想一样，只是访问结点的位置变了

public void inorderTraversal(TreeNode root) {        LinkedList
    
      stack = new LinkedList<>();        while(root != null || !stack.isEmpty()){            while(root != null){                stack.push(root);                root = root.left;            }            root = stack.pop();            visit(root);            root = root.right;        }        return ans;    }
    

2、 思想同1，写法稍有不同

public void inorderTraversal(TreeNode root) {        LinkedList
    
      stack = new LinkedList<>();        while(root != null || !stack.isEmpty()){            if(root != null){                stack.push(root);                root = root.left;            }else{                root = stack.pop();                visit(root);                root = root.right;            }        }    }
    

3、如果可以改变数的结构，那么可以每次把左右子树压栈后，将当前结点左右子结点设为空

public void inorderTraversal(TreeNode root) {        LinkedList
    
      stack = new LinkedList<>();        if(root == null)            return ;        stack.push(root);        while(!stack.isEmpty()){            root = stack.pop();            if(root.left == null && root.right == null){                visit(root);                continue;                            }            if(root.right != null)                stack.push(root.right);            stack.push(root);            if(root.left != null)                stack.push(root.left);            root.left = null;            root.right = null;                    }    }
    

后序遍历（postorder）

1、可以利用同前序遍历的思想，依次访问结点、左子树、右子树，不过因为当前结点需要最后访问，所有可以把访问结果放在栈中，然后当遍历完成后从栈顶开始访问。

public List
    
      postorderTraversal(TreeNode root) {        LinkedList
     
       stack = new LinkedList<>();        LinkedList
      
        ans = new LinkedList<>();        while(root != null || !stack.isEmpty()){            while(root != null){                stack.push(root);                ans.offerFirst(root.val);                root = root.right;            }            root = stack.pop();            root = root.left;        }        return ans;    }
      
     
    

2、同样也可以直接将左右子树压栈，结果也压榨，同preorder 1

public List
    
     preorder(TreeNode root){        LinkedList
     
       ans = new LinkedList<>();        if(root == null)            return ans;        LinkedList
      
        stack = new LinkedList<>();        stack.push(root);        while(!stack.isEmpty()){            root = stack.pop();            ans.offerFirst(root.val);            if(root.right != null)                stack.push(root.right);            if(root.left != null)                stack.push(root.left);        }    }
      
     
    

3、同中序遍历3，如果可以修改树，那么可以每次把左右子树压栈后，将当前结点左右子结点设为空

public void inorderTraversal(TreeNode root) {        LinkedList
    
      stack = new LinkedList<>();        if(root == null)            return ;        stack.push(root);        while(!stack.isEmpty()){            root = stack.pop();            if(root.left == null && root.right == null){                visit(root);                continue;                            }            if(root.right != null)                stack.push(root.right);            if(root.left != null)                stack.push(root.left);            stack.push(root);            root.left = null;            root.right = null;                    }    }