094.Binary Tree Inorder Traversal

  1. Binary Tree Inorder Traversal

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

For example:
Given binary tree [1,null,2,3],

1
2
3
4
5
1
\
2
/
3

return [1,3,2].

//https://leetcode.com/problems/binary-tree-inorder-traversal/description/
//两个思路:1、递归。2、非递归,借用栈

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {
public:
void inorder(TreeNode* root, vector<int> &answer) {
if (root == NULL) {
return;
}
inorder(root->left, answer);
answer.push_back(root->val);
inorder(root->right, answer);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> answer;
inorder(root, answer);
return answer;
}
};
/*
中序遍历非递归:
1、借助栈,将整个树的左边界依次入栈(root=root->left)
2、若root为空,则弹出栈顶node并打印,另root=node.right,然后重复1
3、直到栈为空或root为空,结束
*/
class Solution1 {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> answer;
stack<TreeNode>temp;
while (!temp.empty() || root) {
if (root) {
temp.push(*root);
root = root->left;
}
else {
answer.push_back(temp.top().val);
root = temp.top().right;
temp.pop();
}
}
return answer;
}
};
int main() {
TreeNode *a = new TreeNode(1);
TreeNode *b = new TreeNode(2);
TreeNode *c = new TreeNode(3);
a->right = b;
b->left = c;
Solution1 test;
vector<int> answer = test.inorderTraversal(a);
for (int i = 0; i < answer.size(); i++) {
cout << answer[i]<<" ";
}
return 0;
}

094.Binary Tree Inorder Traversal

https://iii.run/archives/232dfaa567c7.html

作者

mmmwhy

发布于

2018-04-18

更新于

2021-05-30

许可协议

评论