剑指 Offer:07. 重建二叉树

2021年11月25日 阅读数:4
这篇文章主要向大家介绍剑指 Offer:07. 重建二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1. 题目

剑指 Offer 07. 重建二叉树java

2. 描述

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。ide

例如,给出ui

前序遍历 preorder = [3,9,20,15,7]spa

中序遍历 inorder = [9,3,15,20,7]指针

返回以下的二叉树:code

 3
/ \\

9 20
/ \
15 7递归

限制:索引

0 <= 节点个数 <= 5000leetcode

3. 实现方法

3.1 方法 1

3.1.1 思路

  1. 利用指针
  2. 前序遍历的第一个元素确定是二叉树的根节点,我么能够查找该节点在中序遍历中的位置,而后拆分出左右子树;
  3. 其中用一个指针用于指向根节点所在索引位置,而后根据该指针位置来拆分左右子树;
  4. 最后递归求出左右子树便可;

3.1.2 实现

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return recursive(0, 0, inorder.length - 1, preorder, inorder);
}

public TreeNode recursive(int preStart, int inStart, int inEnd, int[] preOrder, int[] inOrder){
    // 
    if(inStart > inEnd || preStart > preOrder.length - 1){
        return null;
    }

    // 建立根节点,根节点即为先序遍历中的第一个元素
    TreeNode root = new TreeNode(preOrder[preStart]);
    // 用于存储不一样子树的根节点的索引位置
    int index = 0;

    // 在中序遍历中找到根节点 root 的位置,而后拆分出来左右子树
    for(int i = inStart; i <= inEnd; i++){
        if(root.val == inOrder[i]){
            // 此时 root 在中序遍历中的索引位置为 i
            index = i;
            break;
        }
    }

    // 递归拆分左右子树
    // index-instart+1 就是当前节点左子树的数量加上当前节点的数量
    // 因此preStart+(index-instart+1)就是当前节点右子树前序遍历开始的位置

    root.left = recursive(preStart + 1, inStart, index - 1, preOrder, inOrder);
    root.right = recursive(preStart + index - inStart + 1, index + 1, inEnd, preOrder,inOrder);

    return root;
}