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
}

相关问题

题目来源