leetcode-105-Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal

发表于   |  

描述

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

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

分析

二叉树的前、中、后3种遍历序列中的前中，中后两对遍历序列可以唯一确定一颗二叉树。对于本题目，根据前序遍历和中序遍历的二叉树构建二叉树，可以先用一个具体的例子来思考，来确定边界值。例如一个二叉树的先序遍历输出序列是：A, B, C, D, E, F, G, H，中序遍历输出序列是：C, B, E, D, F, A, H, G。可以确定的是，A 是根节点，而从中序遍历的序列来看，C, B, E, D, F 在根节点的左边，H, G 在根节点的右边，先序遍历的序列去掉 A 之后，同样可以分成两拨，而且两拨的第一个节点都是根节点，分别是 C，H，到这已经很清楚了，这是一个递归的过程。

解决方案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>& preorder, vector<int>& inorder) {
        return buildTreeWithPreandIn(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
    
    TreeNode* buildTreeWithPreandIn(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end) {
        if(pre_start > pre_end) {
            return NULL;
        }
        int pre_first_result = preorder[pre_start];
        int root_position = in_start;
        for (; root_position < in_end; root_position++) {
            if(inorder[root_position] == pre_first_result) {
                break;
            }
        }
        TreeNode* node = new TreeNode(pre_first_result);
        int left_length = root_position - in_start;
        int right_length = in_end - root_position;
        node->left = buildTreeWithPreandIn(preorder, inorder, pre_start+1, pre_start+left_length, in_start, root_position-1);
        node->right = buildTreeWithPreandIn(preorder, inorder, pre_end-right_length+1, pre_end, root_position+1, in_end);
        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
/**
 * 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[] preorder, int[] inorder) {
        return buildTreeWithPreandIn(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    
    public TreeNode buildTreeWithPreandIn(int[] preorder, int[] inorder, int pre_start, int pre_end, int in_start, int in_end) {
        if(pre_start > pre_end) {
            return null;
        }
        int pre_first_result = preorder[pre_start];
        int root_position = in_start;
        for (; root_position < in_end; root_position++) {
            if(inorder[root_position] == pre_first_result) {
                break;
            }
        }
        
        TreeNode node = new TreeNode(pre_first_result);
        int left_length = root_position - in_start;
        int right_length = in_end - root_position;
        node.left = buildTreeWithPreandIn(preorder, inorder, pre_start+1, pre_start+left_length, in_start, root_position-1);
        node.right = buildTreeWithPreandIn(preorder, inorder, pre_end-right_length+1, pre_end, root_position+1, in_end);
        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(preorder []int, inorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }
    
    res := &TreeNode{
        Val: preorder[0],
    }
    
    if len(inorder) == 1 {
        return res
    }
    
    index := indexOf(res.Val, inorder)
    res.Left = buildTree(preorder[1:index+1], inorder[:index])
    res.Right = buildTree(preorder[index+1:], inorder[index+1:])
    return res
}

func indexOf(val int, nums []int) int {
    for i, v := range nums {
        if v == val {
            return i
        }
    }
    return 0
}

相关问题

题目来源