Leetcode-94 Binary Tree Inorder Traversal

发表于 | 分类于 | 次

Binary Tree Inorder Traversal

Given a binary tree, return the inorder 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,3,2]

解题思路

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

复杂度分析

  • 时间复杂度：$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
class Solution {
public:
	vector<int> inorderTraversal(TreeNode* root) {
		TreeNode *p = root;
		stack<TreeNode*> ps;
		vector<int> res;
		while (p != nullptr || !ps.empty()) {
			if (p != nullptr) { //记录该节点,并遍历左子树
				ps.push(p);
				p = p->left;
			}
			else { //左子树遍历完,打印父节点值,并遍历右子树
				p = ps.top();
				ps.pop();
				res.push_back(p->val);
				p = p->right;
			}
		}
		return res;
	}
};