0%

[Leetcode]94. Binary Tree Inorder Traversal(C++)

题目描述

题目链接:94. Binary Tree Inorder Traversal

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

例子

例子 1

Input: root = [1,null,2,3]
Output: [1,3,2]

例子 2

Input: root = []
Output: []

例子 3

Input: root = [1]
Output: [1]

例子 4

Input: root = [1,2]
Output: [2,1]

例子 5

Input: root = [1,null,2]
Output: [1,2]
Explanation:

Constraints

.The number of nodes in the tree is in the range [0, 100].
.-100 <= Node.val <= 100

Follow Up

Recursive solution is trivial, could you do it iteratively?

解题思路

这道题要求输出二叉树的中序遍历,同样可以利用栈来解决。首先不停往栈中压入所有左节点(相当于树的最左侧),然后从栈顶取出节点再取其右节点进行重复操作。代码如下:

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
#include <stack>
#include <vector>

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
if (!root) return result;

std::stack<TreeNode*> s;
TreeNode* curr = root;
while (!s.empty() || curr) {
while (curr) {
s.push(curr);
curr = curr->left;
}

curr = s.top();
s.pop();
result.push_back(curr->val);
curr = curr->right;
}

return result;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(h)

GitHub 代码同步地址: 94.BinaryTreeInorderTraversal.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions