剑指Offer_07_重建二叉树

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

题目描述

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

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

示例 1:ide

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]ui

示例 2:code

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

限制:leetcode

0 <= 节点个数 <= 5000it

来源:力扣(LeetCode)
连接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcofio

解题思路

题目要求经过前序遍历和中序遍历生成二叉树
前序遍历:先输出根节点,而后再输出左子树和右子树
中序遍历:先输出左子树,而后输出根节点,最后输出右子树
经过观察发现:
一、前序遍历数组的第一个节点是根节点
二、在中序遍历数组中,根节点所在位置左侧的节点属于左子树,右侧节点属于右子树
使用递归实现,找到根节点,而后将剩余节点分为左子树和右子树,不断寻找根节点,拆分剩余节点,直至只有一个节点或没有节点class

代码

class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
          return buildRoot(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        }
        public TreeNode buildRoot(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
            int length = preEnd-preStart;
            if(length<0)return null;
            TreeNode root = new TreeNode(preorder[preStart]);
            if(length==0)return root;
            int pos = 0;
            while(inStart+pos<inEnd){
                if(inorder[inStart+pos]==root.val){
                    break;
                }
                pos++;
            }
            if(pos > 0){

                root.left=buildRoot(preorder,preStart+1,preStart+pos,inorder,inStart,inStart+pos-1);
            }
            if(inStart + pos < inEnd){

                root.right=buildRoot(preorder,preStart+pos+1,preEnd,inorder,inStart+pos+1,inEnd);
            }
            return root;
        }
    }