889. 根据前序和后序遍历构造二叉树

根据前序和后序遍历构造二叉树

• 难度: medium
• 原始链接: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal
• 标签: 分治

解法一: 分治

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
  n1 := len(preorder)
  n2 := len(postorder)
  postIndexMap := make(map[int]int, n2)
  for i, num := range postorder {
    postIndexMap[num] = i
  }
  return dfs(preorder, postIndexMap, 0, n1-1, 0, n2-1)
}

func dfs(preorder []int, postIndexMap map[int]int, preLeft, preRight, postLeft, postRight int) *TreeNode {
  if preLeft > preRight {
    return nil
  }
  root := &TreeNode{
    Val: preorder[preLeft],
  }
  if preLeft < preRight {
    postMid := postIndexMap[preorder[preLeft+1]]
    preMid := preLeft + postMid - postLeft + 1
    root.Left = dfs(preorder, postIndexMap, preLeft+1, preMid, postLeft, postMid)
    root.Right = dfs(preorder, postIndexMap, preMid+1, preRight, postMid+1, postRight-1)
  }
  return root
}

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int n1 = preorder.length;
        int n2 = postorder.length;
        Map<Integer, Integer> postIndexMap = new HashMap<>(n2);
        for (int i = 0; i < n2; i++) {
            postIndexMap.put(postorder[i], i);
        }
        return this.dfs(preorder, postIndexMap, 0, n1 - 1, 0, n2 - 1);
    }

    private TreeNode dfs(int[] preorder, Map<Integer, Integer> postIndexMap, int preLeft, int preRight, int postLeft, int postRight) {
        if (preLeft > preRight) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preLeft]);
        if (preLeft < preRight) {
            int postMid = postIndexMap.get(preorder[preLeft + 1]);
            int preMid = preLeft + postMid - postLeft + 1;
            root.left = this.dfs(preorder, postIndexMap, preLeft + 1, preMid, postLeft, preMid);
            root.right = this.dfs(preorder, postIndexMap, preMid + 1, preRight, postMid + 1, postRight - 1);
        }
        return root;
    }
}