首页 > 编程语言 >算法题:剑指 Offer 07. 重建二叉树(题目+思路+代码+注释)时空时间优先选O(N) O(N) 2ms击败97%、76%用户,空间优先则选O(N*logN) O(1)

算法题:剑指 Offer 07. 重建二叉树(题目+思路+代码+注释)时空时间优先选O(N) O(N) 2ms击败97%、76%用户,空间优先则选O(N*logN) O(1)

时间:2023-12-25 20:36:02浏览次数:44  
标签:2ms 优先 right TreeNode preorder int 二叉树 root left


算法题:剑指 Offer 07. 重建二叉树(题目+思路+代码+注释)时空时间优先选O(N) O(N) 2ms击败97%、76%用户,空间优先则选O(N*logN) O(1)_java

题目

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

算法题:剑指 Offer 07. 重建二叉树(题目+思路+代码+注释)时空时间优先选O(N) O(N) 2ms击败97%、76%用户,空间优先则选O(N*logN) O(1)_数据结构_02

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制:

0 <= 节点个数 <= 5000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

题目中的null你可能不太理解,那是打印的算法上,与直接理解打印数不一样,他打印了非叶子节点的左右节点,空的就是null,这个不在乎这么多,我们要的是重建这颗二叉树并且返回根节点对象就可以了

第一步观察数据,根据二叉树遍历特性找规律,逆向解出来。

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

首先第一点,在前序遍历的时候第一个数字一定是根节点,那么我们拿到了根节点,如何去获取左右的子节点呢?

根据中序遍历的特性,根节点在最中间,因此我们拿着从前序遍历里得到的3到中序遍历里找到3的下标,于是乎在中序遍历里3的左边的数字全部属于左子树,3右边的数字全部是右子树的。也就是左边的9是左子树,15 20 7是右子树,这样我们就知道了左右子树有多少个数字了,回到前序遍历中,前序遍历是: 根节点 左子树 右子树,而左子树的第一个就是根节点的左子节点,右子树的第一个就是右子树的第一个节点,因此我们就可以找出根节点的左右节点,按照这个方法递归下去,就能把每个节点的左右节点找出来,最后整颗二叉树就建好了。我们详细步骤来解释下:

算法题:剑指 Offer 07. 重建二叉树(题目+思路+代码+注释)时空时间优先选O(N) O(N) 2ms击败97%、76%用户,空间优先则选O(N*logN) O(1)_子树_03

代码

提交代码

/**
 * 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 == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        HashMap<Integer,Integer> map = new HashMap<>(preorder.length);
        for (int i = 0,len = preorder.length; i < len;i++){
            map.put(inorder[i],i);
        }
        rebuild(map,root,preorder,inorder,0,0,preorder.length-1);
        return root;
    }

    /**
     * 重建二叉树函数
     * @param map 中序遍历 k:数字 v:下标
     * @param root 当前子树的根节点对象
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @param rootInPreOrderIndex  根节点在前序遍历数组中的下标
     * @param left 当前root点为根节点的子树在中序遍历数组中的起始下标
     * @param right 当前root点为根节点的子树在中序遍历数组中的终止下标
     */
    public void rebuild(HashMap<Integer,Integer> map,TreeNode root,int[] preorder, int[] inorder,int rootInPreOrderIndex,int left,int right){
        if (left < right){
            int rootNum = preorder[rootInPreOrderIndex];
            int rootInOrderIndex = map.get(rootNum);
            int leftTreeSize = rootInOrderIndex - left;
            int rightTreeSize = right - rootInOrderIndex;
            /*System.out.println("当前节点"+rootNum+" root在先序遍历上的下标:"+rootInPreOrderIndex+"左右子树在中序遍历上的 left:"+left+" right:"+right+" 左子树大小:"+leftTreeSize+" 右子树大小:"+rightTreeSize);
            System.out.println("整颗树");
            for (int i = left; i<= right;i++){
                System.out.print(preorder[i]+" ");
            }
            System.out.println();
            System.out.println("左子树");
            for (int i = 0; i< leftTreeSize;i++){
                System.out.print(preorder[left+i+1]+" ");
            }
            System.out.println();
            System.out.println("右子树");
            for (int i = 0; i< rightTreeSize;i++){
                System.out.print(preorder[left+leftTreeSize+i+1]+" ");
            }
            System.out.println();*/
            //左子树
            if (leftTreeSize > 0){
                TreeNode leftNode = new TreeNode(preorder[rootInPreOrderIndex+1]);
                root.left = leftNode;
                //以左节点为根继续递归建立子树
                rebuild(map,root.left,preorder,inorder,rootInPreOrderIndex+1,left,rootInOrderIndex-1);
            }
            //右子树
            if (rightTreeSize > 0){
                TreeNode rightNode = new TreeNode(preorder[rootInPreOrderIndex+leftTreeSize+1]);
                root.right = rightNode;
                rebuild(map,root.right,preorder,inorder,rootInPreOrderIndex+leftTreeSize+1,rootInOrderIndex+1,right);
            }
        }
    }
}

测试代码(有提示打印)

附带对二叉树前序遍历、中序遍历、后序遍历的打印函数以供测试用
对递归中执行的每一步打印输出关键数据,便于理解,解除注释即可

package leetcode.offer.q07;

import java.util.HashMap;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        HashMap<Integer,Integer> map = new HashMap<>(preorder.length);
        for (int i = 0,len = preorder.length; i < len;i++){
            map.put(inorder[i],i);
        }
        rebuild(map,root,preorder,inorder,0,0,preorder.length-1);
        return root;
    }

    /**
     * 重建二叉树函数
     * @param map 中序遍历 k:数字 v:下标
     * @param root 当前子树的根节点对象
     * @param preorder 前序遍历数组
     * @param inorder 中序遍历数组
     * @param rootInPreOrderIndex  根节点在前序遍历数组中的下标
     * @param left 当前root点为根节点的子树在中序遍历数组中的起始下标
     * @param right 当前root点为根节点的子树在中序遍历数组中的终止下标
     */
    public void rebuild(HashMap<Integer,Integer> map,TreeNode root,int[] preorder, int[] inorder,int rootInPreOrderIndex,int left,int right){
        if (left < right){
            int rootNum = preorder[rootInPreOrderIndex];
            int rootInOrderIndex = map.get(rootNum);
            int leftTreeSize = rootInOrderIndex - left;
            int rightTreeSize = right - rootInOrderIndex;
            /*System.out.println("当前节点"+rootNum+" root在先序遍历上的下标:"+rootInPreOrderIndex+"左右子树在中序遍历上的 left:"+left+" right:"+right+" 左子树大小:"+leftTreeSize+" 右子树大小:"+rightTreeSize);
            System.out.println("整颗树");
            for (int i = left; i<= right;i++){
                System.out.print(preorder[i]+" ");
            }
            System.out.println();
            System.out.println("左子树");
            for (int i = 0; i< leftTreeSize;i++){
                System.out.print(preorder[left+i+1]+" ");
            }
            System.out.println();
            System.out.println("右子树");
            for (int i = 0; i< rightTreeSize;i++){
                System.out.print(preorder[left+leftTreeSize+i+1]+" ");
            }
            System.out.println();*/
            //左子树
            if (leftTreeSize > 0){
                TreeNode leftNode = new TreeNode(preorder[rootInPreOrderIndex+1]);
                root.left = leftNode;
                //以左节点为根继续递归建立子树
                rebuild(map,root.left,preorder,inorder,rootInPreOrderIndex+1,left,rootInOrderIndex-1);
            }
            //右子树
            if (rightTreeSize > 0){
                TreeNode rightNode = new TreeNode(preorder[rootInPreOrderIndex+leftTreeSize+1]);
                root.right = rightNode;
                rebuild(map,root.right,preorder,inorder,rootInPreOrderIndex+leftTreeSize+1,rootInOrderIndex+1,right);
            }
        }
    }

    /**
     * 前序遍历
     * @param root
     */
    public void preOrderPrintTree(TreeNode root){
        if (root != null){
            System.out.print(root.val+" ");
            if (root.left != null){
                preOrderPrintTree(root.left);
            }
            if (root.right != null){
                preOrderPrintTree(root.right);
            }
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrderPrintTree(TreeNode root){
        if (root != null){
            if (root.left != null){
                inOrderPrintTree(root.left);
            }
            System.out.print(root.val+" ");
            if (root.right != null){
                inOrderPrintTree(root.right);
            }
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    public void sufOrderPrintTree(TreeNode root){
        if (root != null){
            if (root.left != null){
                sufOrderPrintTree(root.left);
            }
            if (root.right != null){
                sufOrderPrintTree(root.right);
            }
            System.out.print(root.val+" ");
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        //前序遍历、中序遍历、后序遍历示范
        /*TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        TreeNode tmp = root.right;
        tmp.left = new TreeNode(15);
        tmp.right = new TreeNode(7);
        solution.preOrderPrintTree(root);
        System.out.println();
        solution.inOrderPrintTree(root);
        System.out.println();
        solution.sufOrderPrintTree(root);*/

        int[] preOrder = {1,2,3};
        int[] inOrder = {3,2,1};
        TreeNode root = new Solution().buildTree(preOrder,inOrder);
        solution.preOrderPrintTree(root);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

空间优先代码(去掉了哈希表,手动在子树内搜索下标)

/**
 * 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 == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        rebuild(root,preorder,inorder,0,0,preorder.length-1);
        return root;
    }

    public void rebuild(TreeNode root,int[] preorder, int[] inorder,int rootIndex,int left,int right){
        if (left < right){
            int rootNum = root.val;
            int rootInOrderIndex = left;
            while (rootInOrderIndex <= right){
                if (inorder[rootInOrderIndex] == rootNum){
                    break;
                }else {
                    rootInOrderIndex++;
                }
            }
            int leftTreeSize = rootInOrderIndex - left;
            int rightTreeSize = right - rootInOrderIndex;
            /*System.out.println("当前节点"+rootNum+" root在先序遍历上的下标:"+rootInPreOrderIndex+"左右子树在中序遍历上的 left:"+left+" right:"+right+" 左子树大小:"+leftTreeSize+" 右子树大小:"+rightTreeSize);
            System.out.println("整颗树");
            for (int i = left; i<= right;i++){
                System.out.print(preorder[i]+" ");
            }
            System.out.println();
            System.out.println("左子树");
            for (int i = 0; i< leftTreeSize;i++){
                System.out.print(preorder[left+i+1]+" ");
            }
            System.out.println();
            System.out.println("右子树");
            for (int i = 0; i< rightTreeSize;i++){
                System.out.print(preorder[left+leftTreeSize+i+1]+" ");
            }
            System.out.println();*/
            //左子树
            if (leftTreeSize > 0){
                TreeNode leftNode = new TreeNode(preorder[rootIndex+1]);
                root.left = leftNode;
                //以左节点为根继续递归建立子树
                rebuild(root.left,preorder,inorder,rootIndex+1,left,rootInOrderIndex-1);
            }
            //右子树
            if (rightTreeSize > 0){
                TreeNode rightNode = new TreeNode(preorder[rootIndex+leftTreeSize+1]);
                root.right = rightNode;
                rebuild(root.right,preorder,inorder,rootIndex+leftTreeSize+1,rootInOrderIndex+1,right);
            }
        }
    }
}


标签:2ms,优先,right,TreeNode,preorder,int,二叉树,root,left
From: https://blog.51cto.com/humorchen/8971728

相关文章

  • 树与二叉树与森林
    2、若将一棵树T转化为对应的二叉树BT,则下列对BT的遍历中,其遍历序列与T的后根遍历序列相同的是______。A.先序遍历B.中序遍历C.后序遍历D.按层遍历解析:在后根遍历(也称为后序遍历或后序遍历)中,对于T的每个节点,首先遍历其左子树,然后遍历其右子树,最后访问该节点本身。而在中根......
  • NTP时间服务器优先级配置
    先思考一个问题:当一个客户端配置向多个NTP时间服务器校时,此时客户端优先向哪个时间服务器同步时间呢?一个完整的NTP校时请求分四步:1、客户端向服务器发起校时请求2、服务器收到客户端发送的校时请求3、服务器处理客户端的校时请求并发送(响应)给客户端4、客户端收到服务器响应的......
  • 二叉树 - 基本概念
    1.树的基本概念与数组链表不同,树是一种非线性的存储结构,它由n(n>=0)个节点构成并具有层次关系的存储结构把这个存储结构叫做树是因为它看上去像一颗倒挂着的树,只是根在上叶子在下它有以下特性:1. 有一个特殊的结点,称为根结点,根结点没有前驱结点2.树是由若干不相交的......
  • 完全二叉树的公共父结点
    1.有点后序遍历的思想,就是先把左子树,右子树的结果算出来,然后合并到根节点。2.合并时四种情况分类讨论.3.对于遇到要找的点就可以直接返回,不管另一个点在这个点下面还是在别的子树上,都是正确的intn,m;inta[N];intquery(introot,intx,inty){ //cerr<<root<<endl; if(r......
  • 637. 二叉树的层平均值
    目录题目题解:BFS题目给定一个非空二叉树的根节点root,以数组的形式返回每一层节点的平均值。与实际答案相差10-5以内的答案可以被接受。题解:BFSclassSolution:defaverageOfLevels(self,root:Optional[TreeNode])->List[float]:q=[root]#用列表做......
  • 二叉树给出先序和中序遍历序列,求和树 要求输出中序遍历序列;
    1.就算不知道用vector的初始化,也可以手动赋值创建子数组。2.不断找到当前序列对应的根节点,计算他的子节点的总和,在这样递归处理过程中,注意要中序输出,所以对于是先遍历完左子树,然后输出答案,然后遍历右子树#include<bits/stdc++.h>usingnamespacestd;#definelllonglong//......
  • 二叉树已经知道先序中序推后序
    https://www.acwing.com/problem/content/3601/不断找新的先序的根节点,根据位置切割中序,根据中序左右子树大小反切割先序,找到左子树对应的先序中序,然后递归处理#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include<algorithm>#include<iostream>......
  • C++U5-11-特殊二叉树
    学习目标 完全二叉树:二又树拥有的性质,在完全二叉树中都拥有 性质 练习1 练习2 练习3编程题:[完全二叉树的叶子结点]【算法分析】递归,前序遍历输出。【参考代码】#include<iostream>usingnamespacestd;constintSIZE=1010;structnode{......
  • 662. 二叉树最大宽度(中)
    目录题目题解:BFS正解:优化题目给你一棵二叉树的根节点root,返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每一层的宽度被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的null......
  • 543. 二叉树的直径
    给你一棵二叉树的根节点,返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。 示例1:输入:root=[1,2,3,4,5]输出:3解释:3,取路径[4,2,1,3]或[5,2,1,......