HOME/剑指Offer/

1.重建二叉树

Article Outline
TOC
Collection Outline

1.重建二叉树

1.1关于二叉树:

  • 二叉树前序遍历:先访问根节点,在访问左子节点,最后访问右子节点

  • 二叉树中序遍历:先访问左子节点,在访问根节点,最后访问右子节点

  • 二叉树后续遍历:先访问左子节点,在访问右子节点,最后访问根节点

  • 关于遍历,一般都有递归和循环,但是递归比循环简单。

  • 二叉树的特性:左子节点总是小于或等于根节点,右子节点是大于或等于根节点

  • 二叉树的两个特例:堆和红黑树。堆分为最大堆(根节点值最大)和最小堆(根节点值最小)。

1.2题目描述:

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

1.3解题思路:

因为是树的结构,一般都是用递归来实现。

用数学归纳法的思想就是,假设最后一步,就是root的左右子树都已经重建好了,那么我只要考虑将root的左右子树安上去即可。

根据前序遍历的性质,第一个元素必然就是root,那么下面的工作就是如何确定root的左右子树的范围。

根据中序遍历的性质,root元素前面都是root的左子树,后面都是root的右子树。那么我们只要找到中序遍历中root的位置,就可以确定好左右子树的范围。

正如上面所说,只需要将确定的左右子树安到root上即可。递归要注意出口,假设最后只有一个元素了,那么就要返回。

1573283943019

1.4代码实现:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution{
    public TreeNode resConStructBinaryTree(int[] pre,in t[] in){
        //数组长度为0
        if(pre.length == 0){
            return null;
        }
        //找到中间值
        int rootVal = pre[0];
        //数组长度仅为1 则返回该节点
        if(pre.length == 1){
            return new TreeNode(rootVal);
        }
        //确定根节点的位置,接着确定左子树和右子树的范围
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = 0;
        for(int i = 0 ; i < in.length; i++){
            if(rootVal == in[i]){
                rootIndex = i;
                break;
            }
        }

        //递归处理 将左右子树放到root的 左右
        root.left = resConStructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
                root.right = resConStructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));
    }
}