leetcode-94-Binary-Tree-Inorder-Traversal

描述


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

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
\
2
/
3

return [1,3,2].

分析


中序遍历,利用堆栈即可解决

解决方案1(C++)


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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode *p = root;
stack<TreeNode *> s;
while(!s.empty() || p != NULL) {
if(p != NULL) {
s.push(p);
p = p->left;
}else {
p = s.top();
s.pop();
result.push_back(p->val);
p = p->right;
}
}
return result;
}
};

相关问题


(M) Kth Smallest Element in a BST
(M) Validate Binary Search Tree
(H) Closest Binary Search Tree Value II
(M) Binary Tree Preorder Traversal
(H) Binary Tree Postorder Traversal
(M) Binary Search Tree Iterator
(M) Inorder Successor in BST

题目来源