Binary Tree Inorder

You cannot find peace by avoiding life.

1. 题目:二叉树中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

2. 解析:

原来还想先找到左下角的节点,再按中序的顺序遍历的。后来发现想多了,直接递归遍历,每次遇到中序节点就添加到 vector 中,最后结果返回中序遍历节点元素数组。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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>

using namespace std;

typedef struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;

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

TreeNode *getLBNode(TreeNode *root);

void inorder(TreeNode *root);

vector<int> all;

/**
*
* @param root node of tree
* @return
*/
vector<int> inorderTraversal(TreeNode *root) {
inorder(root);
return all;
}

void inorder(TreeNode *root) {
if (root != NULL) {
if (root->left != NULL) {
inorder(root->left);
}
cout << root->val;
all.push_back(root->val);
if (root->right != NULL) {
inorder(root->right);
}
}
}

TreeNode *getLBNode(TreeNode *root) {
TreeNode *tmp = root;
if (tmp != NULL) {
while (tmp->left != NULL) {
tmp = tmp->left;
}
}
return tmp;
}

3. 测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
int main() {
TreeNode *node1 = new TreeNode(1);
TreeNode *node2 = new TreeNode(2);
TreeNode *node3 = new TreeNode(3);

node1->left = NULL;
node1->right = node2;
node2->left = node3;

inorder(node1);
return 0;
}

直接运行会输出:

1
132

正确。权当复习。


THE END.

评论