二叉树遍历

二叉树的非递归遍历

前序遍历

/**
* 按照 根-左-右 的模式遍历一棵二叉树称为前序遍历
* 在非递归实现的时候要注意，用栈来保存访问过的节点，应该按照 先右孩子 后左孩子的顺序入栈
* 这样就可使得出栈时候 先访问到的是左孩子，然后才是右孩子。
*/
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return  res;    
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            res.add(root.val);
            if(root.right !=null){
                stack.push(root.right);
            }
            if(root.left!=null){
                stack.push(root.left);
            }
        }
        return res;
    }

中序遍历

/**
* 按照 左-根-右 模式遍历二叉树称为中序遍历
* 在非递归实现的时候要结合递归方式
*          inorder(root.left);
*          visit(root);
*		  inorder(root.right);
* 我们需要先将保存左孩子，直到最左孩子并讲他们依次加入栈，然后pop栈顶元素访问，然后操作最左孩子的右孩子。
*/
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

后序遍历

/**
* 按照 左-右-根的模式访问一棵二叉树成为后序遍历
* 后序遍历的非递归模式可以根据 按照前序遍历的模式巧妙的实现
* 在前序遍历的时候 按照 根-左-右 遍历的
* 我们可以将前序遍历中左右孩子的入站顺便颠倒一下，就会得到 根-右-左 的遍历结果
* 而 根-右-左 恰好是 后序遍历 左-右-根 的逆序。从而就可以得到后序遍历的结果。
*/
public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        Deque<Integer> q = new ArrayDeque<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            q.push(root.val);
            if(root.left!=null){
                stack.push(root.left);
            }
            if(root.right!=null){
                stack.push(root.right);
            }
        }
        while(q.size()>0){
            res.add(q.pop());
        }
        return res;
    }