美文网首页计算机杂谈程序员
剑指offer----重建二叉树

剑指offer----重建二叉树

作者: qming_c | 来源:发表于2018-02-02 14:21 被阅读0次

题目输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

我的解法:

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return fun(pre, in, 0, pre.length,0 ,in.length -1 );
    }
    private TreeNode fun(int[] pre, int[] in, int preLeftIndex,int preRightIndex, int inLeftIndex, int inRightIndex){
        if(inLeftIndex > inRightIndex   || preLeftIndex  > preRightIndex){
            return null;
        }
        TreeNode root = new TreeNode(pre[preLeftIndex]);
        for(int i = inLeftIndex; i <= inRightIndex; i++){
            if(in[i] == pre[preLeftIndex]){
                root.left = fun(pre, in, preLeftIndex + 1, preLeftIndex + i - inLeftIndex, inLeftIndex, i - 1 );
                root.right = fun(pre, in, preLeftIndex + i - inLeftIndex + 1, preRightIndex,i + 1, inRightIndex);
                break;
            }
        }
        return root;
    }
}
思路:

二叉树的前序遍历和中序遍历

  • 前序遍历:先访问当前节点,然后以前序访问左子树,右子树。
  • 中序遍历:先以中序遍历左子树,接着访问当前节点,然后以中序遍历右子树。

所以前序遍历的特点为:前序遍历的每一个节点都是当前子树的根节点,同时,以中序遍历中该节点为边界,可以把中序遍历的结果分为左子树和右子树

  • 前序遍历序列{*1,2,4,7,3,5,6,8}
  • 中序遍历序列{4,7,2,*1,5,3,8,6}

前序遍历的第一个节点将中序遍历的结果分成了{4,7,2}和{5,3,8,6}两部分,他就是以1为根的左右两个子树的全部节点
然后接着将其子树按照上述方法进行拆分,就可以获得原始的树结构了。
注:此种解法要保证在树中无重复节点
几个需要注意的点:

  • 边界检查
  • 如过要想复原一颗二叉树,需要知道他的前/后序遍历+中序遍历 因为前序和后序本质上是一样的,只有应用两种性质不一致的方式才能复原二叉树。

相关文章

  • 剑指offer----重建二叉树

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

  • LeetCode | 面试题07. 重建二叉树【剑指Offer】

    LeetCode 面试题07. 重建二叉树【剑指Offer】【Medium】【Python】【二叉树】【递归】 问...

  • 剑指Offer(四)

    剑指Offer(四) 重建二叉树 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的...

  • 重建二叉树

    《剑指offer》面试题7:重建二叉树 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前...

  • 71.重建二叉树

    day18: 剑指 Offer 07. 重建二叉树[https://leetcode-cn.com/prob...

  • 剑指Offer 07. 重建二叉树

    剑指 Offer 07. 重建二叉树 题目传送门[https://leetcode-cn.com/problems...

  • 重建二叉树

    上牛客网做了一道剑指offer的算法题 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设...

  • 剑指Offer--(5)重建二叉树

    title: 剑指Offer--(5)重建二叉树 categories: 算法与数据结构 tags: 数据结构 题...

  • 剑指offer----树

    重建二叉树:根据前序和中序遍历的结果重建二叉树。假设输入的遍历结果都不含有重复的数字。 二叉树的下一个节点:给定一...

  • 剑指offer----递归

    斐波那契数列:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)...

网友评论

    本文标题:剑指offer----重建二叉树

    本文链接:https://www.haomeiwen.com/subject/fmxezxtx.html