leetcode-106-Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal

描述


Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

分析


基本上思路跟 105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal 是一样的,还是用那个二叉树的例子,这里的后序遍历输出序列是 C, E, F, D, B, H, G, A,A 显而易见是根节点,根据中序遍历序列 C, B, E, D, F, A, H, G ,根节点 A 左边是 C, E, F, D, B,右边是 H, G。

解决方案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
30
31
32
33
34
/**
* 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:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTreeWithInandPost(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
}
TreeNode* buildTreeWithInandPost(vector<int>& inorder, vector<int>& postorder, int in_start, int in_end, int post_start, int post_end) {
if(post_start > post_end) {
return NULL;
}
int post_last_result = postorder[post_end];
int root_position = in_start;
for (; root_position < in_end; root_position++) {
if(inorder[root_position] == post_last_result) {
break;
}
}
TreeNode* node = new TreeNode(post_last_result);
int left_length = root_position - in_start;
int right_length = in_end - root_position;
node->left = buildTreeWithInandPost(inorder, postorder, in_start, root_position-1, post_start, post_start+left_length-1);
node->right = buildTreeWithInandPost(inorder, postorder, root_position+1, in_end, post_end-right_length, post_end-1);
return node;
}
};

解决方案2(Java)


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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTreeWithPreandIn(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
}
public TreeNode buildTreeWithPreandIn(int[] inorder, int[] postorder, int in_start, int in_end, int post_start, int post_end) {
if (post_start > post_end) {
return null;
}
int post_last_result = postorder[post_end];
int root_position = in_start;
for (; root_position < in_end; root_position++) {
if(inorder[root_position] == post_last_result) {
break;
}
}
TreeNode node = new TreeNode(post_last_result);
int left_length = root_position - in_start;
int right_length = in_end - root_position;
node.left = buildTreeWithPreandIn(inorder, postorder, in_start, root_position-1, post_start, post_start+left_length-1);
node.right = buildTreeWithPreandIn(inorder, postorder, root_position+1, in_end, post_end-right_length, post_end-1);
return node;
}
}

解决方案3(Golang)


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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder) == 0 {
return nil
}
res := &TreeNode {
Val: postorder[len(postorder)-1],
}
if len(inorder) == 1 {
return res
}
index := indexOf(res.Val, inorder)
res.Left = buildTree(inorder[:index], postorder[:index])
res.Right = buildTree(inorder[index+1:], postorder[index:len(postorder)-1])
return res
}
func indexOf(val int, nums []int) int {
for i, v := range nums {
if v == val {
return i
}
}
return 0
}

相关问题


(M) Construct Binary Tree from Preorder and Inorder Traversal

题目来源