模拟栈方法实现二叉树先中后序遍历

递归遍历回顾

alt text

1
2
3
4
5
6
7
8
9
public void dfs(treenode root){
    if(root == null) return;
    //先序 sout(root)
    dfs(root.left);
    //中序 sout(root)
    dfs(root.right);
    //后序 sout(root)

}

利用栈模拟递归过程

先中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
            TreeNode p=root;
        ArrayDeque<TreeNode> cache = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        while(true){
            //终止条件
            if(cache.isEmpty() && p==null){
                return ans;
            }
            if(p!=null){
                cache.push(p);
                //先序ans.adad(p.val);
                p=p.left;
            }else{
                TreeNode pop = cache.pop();
                //中序 ans.adad(p.val);
                p=pop.right;
            }
        }

    }
}


后序

  • 后序遍历需要用到一个记录状态的指针memo
  • 如果memo指针指向右子树说明右子树处理完了直接返回,栈弹出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root, memo = null;
    while (p != null || !stack.isEmpty()) {
        if(p!=null){
            stack.push(p);
            p=p.left;
        }else{
            TreeNode peek = stack.peek();
            //返回条件
            if(peek.right==memo || peek.right==null){
                //懒操作
                TreeNode pop = stack.pop();
                ans.add(pop.val);
                memo=pop;
            }else{
                //懒操作直到右节点满足条件p才真正转移过去
                p=peek.right;
            }
        }
    }
    return ans;
}