105. 从前序与中序遍历序列构造二叉树

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

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

解法一: 分治

go

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

func dfs(preorder []int, inorderMap map[int]int, preLeft, preRight, inLeft, inRight int) *TreeNode {
  if preLeft > preRight {
    return nil
  }
  node := &TreeNode{
    Val: preorder[preLeft],
  }
  inMid := inorderMap[preorder[preLeft]]
  preMid := preLeft + inMid - inLeft
  node.Left = dfs(preorder, inorderMap, preLeft+1, preMid, inLeft, inMid-1)
  node.Right = dfs(preorder, inorderMap, preMid+1, preRight, 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[] preorder, int[] inorder) {
        int n1 = preorder.length;
        int n2 = inorder.length;
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>(n2);
        for (int i = 0; i < n2; i++) {
            inorderMap.put(inorder[i], i);
        }
        return this.dfs(preorder, inorderMap, 0, n1 - 1, 0, n2 - 1);
    }

    private TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[preLeft]);
        int inMid = inorderMap.get(preorder[preLeft]);
        int preMid = preLeft + inMid - inLeft;
        node.left = this.dfs(preorder, inorderMap, preLeft + 1, preMid, inLeft, inMid - 1);
        node.right = this.dfs(preorder, inorderMap, preMid + 1, preRight, inMid + 1, inRight);
        return node;
    }

}