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

算法 LeetCode 中等难度深度优先搜索分治算法

算法

发布日期: 2021-12-22

更新日期: 2021-12-22

文章字数: 654

阅读次数:

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

一、题目

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

二、相关链接

三、解题思路

解法：递归+深度优先算法
思路：
- 1.遍历构建左右子树
- 2.先序遍历的第一个结点必是头结点，第二个结点是左子树头结点(如有，递归的前提1)
- 3.中序遍历头结点在中间，左边是左子树，右边是右子树(遍历的前提2)
步骤：
- 1.获取先序遍历第一个结点(即树头结点head)
- 2.根据head去中序遍历找到下标inIndex
- 3.根据inIndex去计算左右子树的范围(各自的左右下标)
- 4.根据第3步计算的左右子树长度去先序遍历找到左右子树
- 5.遍历1234

四、代码

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {

  //用户存中序遍历每个数的下标
  private Map<Integer, Integer> map = new HashMap<>();

  /**
   * @param preorder 先序遍历
   * @param inorder 中序遍历
   * @return 树
   */
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    //也可以用indexOf找到，用哈希表其实是空间换时间的思路
    for (int i = 0; i < inorder.length; i++) {
      map.put(inorder[i], i);
    }

    return this.buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);//理论上先序和后续
  }

  /**
   *
   * @param preorder 先序遍历
   * @param preLeft 当前结点的左子树左下标
   * @param preRight 当前结点的左子树右下标
   * @param inLeft 当前结点的右子树左下标
   * @param inRight 当前结点的右子树右下标
   * @return
   */
  private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
    //最多等于的时候说明左/右子树只有一个结点
    if (preLeft > preRight) {
      return null;
    }

    //先序遍历第一位就是头结点,获得其值
    int head = preorder[preLeft];
    TreeNode treeNode = new TreeNode(head);
    //中序遍历的头结点下标
    int inIndex = map.get(head);

    //递归左子树
    treeNode.left = this.buildTree(preorder, preLeft + 1, inIndex - inLeft + preLeft, inLeft, inIndex - 1);
    //递归右子树
    treeNode.right = this.buildTree(preorder, inIndex - inLeft + preLeft + 1, preRight, inIndex + 1, inRight);

    return treeNode;
  }

  /**
   * 例子：
   *  输入：[3,9,20,15,7]
   *  输出：[9,3,15,20,7]
   */
  public static void main(String[] args) {
    int preorder[] = new int[]{3, 9, 20, 15, 7};
    int inorder[] = new int[]{9, 3, 15, 20, 7};
    //不做打印要求，可debug看树结构
    System.out.println(new ConstructBinaryTreeFromPreorderAndInorderTraversal().buildTree(preorder, inorder));
  }

}