leetcode-二叉树后序非递归

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/binary-tree-postorder-traversal/

　　二叉树的后序遍历迭代（非递归）版。

题目分析

　　二叉树的遍历的递归比较好写，非递归版本通常借助栈实现。既然是后序遍历，对于任何一个节点，首先也访问左子树的所有节点，再访问右子树的所有节点，然后访问本节点。这里我们要用到一个栈和一个两个辅助的指针cur和top。cur代表当前考虑的节点，cur不空的时候会入栈，top为栈顶指针。

　　首先，cur值置为root节点，top置为null，循环的条件是cur不为空或者栈不为空，cur不为空主要是为初始时进入循环。进入循环以后先判断cur指针是否为空

  • 1.cur若不为空，说明需要访问该节点的，但是由于是后序遍历，先将cur入栈，当以后cur的左右子树均访问完时再访问cur，因此把cur更新成cur的左节点
  • 2.cur若为空，左子树访问到了尽头，这时看下栈顶top
    • (1).top的右儿子不为空，那么将cur置为top->right，跳出循环
    • (2).top的右儿子为空，此时top为叶子节点，因此需要访问，之后将此节点弹栈。然后又进入循环，判断出栈的节点是当前栈顶节点的左儿子还是右儿子：
      • a.左儿子，把当前栈顶节点的右儿子赋值给cur，跳出循环
      • b.右儿子，那么要访问栈顶节点，并将此节点弹栈，然后继续循环。

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    //iteratively
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null) {
        	return res;
        }
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !s.empty()) {
        	//leftmost
        	if(cur == null) {
        		top = s.peek();
        		if(top.right != null) {
        			cur = top.right;
        		} else {
        			//while,pop stack
	        		res.add(top.val);
	        		s.pop();
        			while(!s.empty()) {
	        			if(s.peek().left == top) {
	        				cur = s.peek().right;
	        				break;
	        			} else {
	        				top = s.peek();
	        				res.add(top.val);
	        				s.pop();
	        			}
        			}
        		}
        	} else {
        		//push left child into stack
	        	s.push(cur);
	        	cur = cur.left;
        	}
        }
        return res;
    }
}