Skip to content

Latest commit

 

History

History
117 lines (80 loc) · 4.4 KB

105.Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal.md

File metadata and controls

117 lines (80 loc) · 4.4 KB
Raw

问题地址/Problem URL

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

问题介绍/Problem Description

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

前置知识

  • 二叉树

思路/Thinking Path

目标是构造二叉树。

构造二叉树需要根的值、左子树和右子树。

此问题可被抽象为：从前序遍历和中序遍历中找到根节点、左子树和右子树。

先找根： 由前序遍历的性质，第0个节点为当前树的根节点。 再找左右子树： 在中序遍历中找到这个根节点，设其下标为i。由中序遍历的性质，0 ~ i-1 是左子树的中序遍历，i+1 ~ inorder.length-1是右子树的中序遍历。

然后递归求解，终止条件是左右子树为null。

We are going to construct a binary tree from its preorder and inorder traversal.

To build a binary tree, it requires us to creact a new TreeNode as the root with filling in the root value. And then, find its left child and right child recursively until the left or right child is null.

Now this problem is abstracted as how to find the root node, left child and right child from the preorder traversal and inorder traversal.

In preorder traversal, the first node (preorder[0]) is the root of current binary tree. In inorder traversal, find the location of this root which is i. The left sub-tree is 0 to i-1 and the right sub-tree is i+1 to inorder.length-1 in inorder traversal.

Then applying the previous operation to the left and right sub-trees.

关键解析/Key Points

如何在前序遍历的数组里找到左右子树的：

  • 根据前序遍历的定义可知，每个当前数组的第一个元素就是当前子树的根节点的值
  • 在中序遍历数组中找到这个值，设其下标为inRoot
    • 当前中序遍历数组的起点inStart到inRoot之间就是左子树，其长度leftChldLen为inRoot-inStart
    • 当前中序遍历数组的终点inEnd和inRoot之间就是右子树
  • 前序遍历和中序遍历中左子树的长度是相等的，所以在前序遍历数组中，根节点下标preStart往后数leftChldLen即为左子树的最后一个节点，其下标为preStart+leftChldLen，右子树的第一个节点下标为preStart+leftChldLen+1。

PLEASE READ THE CODE BEFORE READING THIS PART

If you can't figure out how to get the index of the left and right child, please read this.

  • index of current node in preorder array is preStart(or whatever your call it), it's the root of a subtree.
  • according to the properties of preoder traversal, all right sub-tree nodes are behine all left sub-tree nodes. The length of left sub-tree can help us to divide left and right sub-trees.
  • the length of left sub-tree can be find in the inorder traversal. The location of current node is inRoot(or whatever your call it). The start index of current inorder array is inStart(or whatever your call it). So, the lenght of the left sub-tree is leftChldLen = inRoot - inStart.

explain

代码/Code

  • Java
/**
 * 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) {
    if (preorder.length != inorder.length) return null;
    
    HashMap<Integer, Integer> map = new HashMap<> ();

    for (int i=0; i<inorder.length; i++) {
      map.put(inorder[i], i);
    }

    return helper(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, map);
  }

  public TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> map) {
    if (preStart>preEnd || inStart>inEnd) return null;
    
    TreeNode root = new TreeNode(preorder[prestart]);
    int inRoot = map.get(preorder[preStart]);
    int leftChldLen = inRoot - inStart;

    root.left = helper(preorder, preStart+1, preStart+leftChldLen, inorder, inStart, inRoot-1, map);
    root.left = helper(preorder, preStart+leftChldLen+1, preEnd, inorder, inRoot+1, inEnd, map);

    return root;
  }
}