二叉树前序、中序、后序遍历非迭代解法

Love The Way You Lie 2022-12-10 07:27 151阅读 0赞

### 二叉树前序、中序、后序遍历非迭代解法 ###

> 经常会有面试官，让你手撕二叉树的前序、中序、后序遍历，当你简单得写了递归的方法，
> 
> 面试官看了看，慢悠悠得抛出**你会迭代的解法吗？**，这时候就需要阅读我这篇文章了。
> 
> 前序和中序遍历，解决方法类似，都是使用栈解决的。后序遍历稍微复杂一点。

#### [二叉树前序遍历][Link 1] ####

class Solution { 
        public List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> list = new ArrayList<Integer>();
            TreeNode p = root;
            Stack<TreeNode> stack = new Stack<>();
            while(p != null || !stack.empty()) { 
                while(p != null) { 
                    stack.push(p); list.add(p.val);
                    p = p.left;
                }
                p = stack.pop();
                p = p.right;
            }
            return list;
        }
    }

#### [二叉树中序遍历][Link 2] ####

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

#### [二叉树后序遍历][Link 3] ####

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
            ArrayList<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            if(root != null) stack.push(root);
            while(!stack.empty()) { 
                TreeNode value = stack.pop();
                list.add(value.val);
                if(value.left != null) stack.push(value.left);
                if(value.right != null) stack.push(value.right);
            }
            ArrayList<Integer> result = new ArrayList<>();
            for(int i = list.size()-1; i >= 0; i--) result.add(list.get(i));
            return result;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/
[Link 2]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[Link 3]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/