leetcode-889-Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal

发表于   |  

描述

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

1
2
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

  • 1 <= pre.length == post.length <= 30
  • pre[] and post[] are both permutations of 1, 2, ..., pre.length.
  • It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

分析

先序遍历和中序遍历，中序遍历和后序遍历这两个组合可以确定原二叉树，这是一个常用到的知识点。

pre 数组的第一个元素和 post 的最后一个元素是根节点，可以遍历 pre，依次作为根节点，同时确定 pre 后面的节点在 post 数组中的位置，该位置左边为 pre 后面的节点的子树，右边是根节点的子树，因此可以使用递归，位置关系可以用 HashMap 进行存储。

解决方案1(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 {
    private int preIndex = 0;
    
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < post.length; i++) {
            map.put(post[i], i);
        }
        return traverse(pre, post, map, 0, pre.length-1);
    }
    
    private TreeNode traverse(int[] pre, int[] post, Map<Integer, Integer> map, int l, int r) {
        if (l > r) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preIndex++]);
        if (l == r) {
            return node;
        }
        int newPostIndex = map.get(pre[preIndex-1]);
        int newRootIndex = map.get(pre[preIndex]);
        node.left = traverse(pre, post, map, l, newRootIndex);
        node.right = traverse(pre, post, map, newRootIndex+1, newPostIndex-1);
        return node;
    }
}

题目来源