Leetcode-145 Binary Tree Postorder Traversal

发表于 | 分类于 | 次

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

Follow up: Recursive solution is trivial, could you do it iteratively?

Example 1

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

解题思路

后根遍历，先遍历左子树，再遍历右子树，最后打印根节点值。迭代法需要用栈记录根节点，当从左子树返回根节点时，需要继续遍历右子树；当从右子树返回根节点时，需要打印根节点值并返回上一层。为区分是从左子树返回还是从右子树返回，定义一个指针指向上一次被访问的节点，在返回根节点时判断根节点的右儿子是否为空或者为上一次被访问的节点。如果是，表明根节点的左右子树均被遍历完，需要打印根节点值并返回上一层；否则，继续遍历右子树。

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

代码

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:
	vector<int> postorderTraversal(TreeNode* root) {
		TreeNode *p = root, *lastTravel = nullptr;
		stack<TreeNode*> ps;
		vector<int> res;
		while (p != nullptr || !ps.empty()) {
			if (p != nullptr) { //一直遍历左子树
				ps.push(p);
				p = p->left;
			}
			else { //左子树为空,遍历右子树
				p = ps.top()->right;
				if (p == nullptr || p == lastTravel) {
					//右子树遍历完,打印根节点值并更新lastTravel,再回到上一层
					lastTravel = ps.top();
					res.push_back(lastTravel->val);
					ps.pop();
					p = nullptr;
				}
			}
		}
		return res;
	}
};