106. 从中序与后序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树

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

解法一: 分治

go

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

func dfs(postorder []int, inorderMap map[int]int, postLeft, postRight, inLeft, inRight int) *TreeNode {
  if postLeft > postRight {
    return nil
  }
  node := &TreeNode{
    Val: postorder[postRight],
  }
  inMid := inorderMap[postorder[postRight]]
  postMid := postRight - inRight + inMid
  node.Left = dfs(postorder, inorderMap, postLeft, postMid-1, inLeft, inMid-1)
  node.Right = dfs(postorder, inorderMap, postMid, postRight-1, inMid+1, inRight)
  return node
}

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 buildTree(int[] inorder, int[] postorder) {
        int n1 = inorder.length;
        int n2 = postorder.length;
        Map<Integer, Integer> inorderMap = new HashMap<>(n1);
        for (int i = 0; i < n1; i++) {
            inorderMap.put(inorder[i], i);
        }
        return this.dfs(postorder, inorderMap, 0, n2 - 1, 0, n1 - 1);
    }

    private TreeNode dfs(int[] postorder, Map<Integer, Integer> inorderMap, int postLeft, int postRight, int inLeft, int inRight) {
        if (postLeft > postRight) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[postRight]);
        int inMid = inorderMap.get(postorder[postRight]);
        int postMid = postRight - inRight + inMid;
        node.left = dfs(postorder, inorderMap, postLeft, postMid - 1, inLeft, inMid - 1);
        node.right = dfs(postorder, inorderMap, postMid, postRight - 1, inMid + 1, inRight);
        return node;
    }
}