Leetcode-144 Binary Tree Preorder Traversal

发表于 | 分类于 | 次

Binary Tree Preorder Traversal

Given a binary tree, return the preorder 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: [1,2,3]

解题思路

先根遍历，先打印根节点值，再遍历左子树，最后遍历右子树。迭代法需要用栈记录根节点作为遍历完左子树的出口，以便在遍历完左子树后，继续遍历右子树。

复杂度分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		TreeNode *p = root;
		stack<TreeNode*> ps;
		vector<int> res;
		while (p != nullptr || !ps.empty()) {
			if (p != nullptr) { //打印节点值,记录该节点,并遍历左子树
				res.push_back(p->val);
				ps.push(p);
				p = p->left;
			}
			else { //左子树遍历完,遍历右子树
				p = ps.top()->right;
				ps.pop();
			}
		}
		return res;
	}
};