抱歉,你查看的文章不存在

【挑战剑指offer】系列04:重建二叉树 原

1. 题干描述

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

2. 回顾遍历二叉树的三种规则

  • 前序遍历:先自己,再左结点,最后右结点
  • 中序遍历:先左结点,再自己,最后右结点
  • 后序遍历:先左结点,再右结点,最后自己

由此可以获得的规律和解题算法:

  1. 前序遍历的第一个结点是root,对于中序遍历的结果中应该是位于中间位置
  2. 获得root后,从中序遍历的结果来看,以root切分,可以得到两棵子树
  3. 之后继续读前序遍历的结果,对应到中序遍历的结果可以继续分割,直到分割时只有一个叶子结点
  4. 以此类推,可以推断出原始的二叉树结构

3. 递归重建二叉树

private static int preValueIndex = 0;
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    //如果子树只有一个结点,证明是叶子
    if (in.length == 1) {
        return new TreeNode(pre[preValueIndex]);
    }

    //既然已经过了上面的判断,证明不是叶子节点,可以建立父结点了
    TreeNode thisNode = new TreeNode(pre[preValueIndex]);
    //确定当前遍历的结点在中序遍历的位置
    int inRootValueIndex = ArrayUtils.indexOf(in, pre[preValueIndex]);
    //重建左子树
    TreeNode leftChildren = null;
    if (0 < inRootValueIndex) {
        //移动前序遍历的游标
        preValueIndex++;
        int[] leftSubTree = ArrayUtils.subarray(in, 0, inRootValueIndex);
        leftChildren = reConstructBinaryTree(pre, leftSubTree);
    }
    //重建右子树
    TreeNode rightChildren = null;
    if ((inRootValueIndex + 1) < in.length) {
        //移动前序遍历的游标
        preValueIndex++;
        int[] rightSubTree = ArrayUtils.subarray(in, inRootValueIndex + 1, in.length);
        rightChildren = reConstructBinaryTree(pre, rightSubTree);
    }
    
    //包装两个子树的父结点(即本身)
    thisNode.left = leftChildren;
    thisNode.right = rightChildren;
    return thisNode;
}

4. 变式:不允许使用递归

public static TreeNode reConstructBinaryTreeWithoutRecurrence(int[] pre, int[] in) {
    Stack<Entry<int[], TreeNode>> stack = new Stack<>();
    int preValueIndex = 0;
    
    //辅助值,用于标记下一个结点是否应该放到右孩子上
    boolean isRightSubTree = false;
    TreeNode root = null;
    int[] arrPointer = in;
    while (!stack.isEmpty() || (arrPointer != null && arrPointer.length > 0)) {
        while (arrPointer != null && arrPointer.length > 0) {
            TreeNode node = new TreeNode(pre[preValueIndex++]);
            int thisNodeValueIndex = ArrayUtils.indexOf(arrPointer, node.val);
            int[] subarray = ArrayUtils.subarray(arrPointer, 0, thisNodeValueIndex);
            //如果栈不为空,证明该结点有父结点
            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek().getValue();
                //如果右孩子标记为true,则当前结点是从下面的if结构中首次过来的
                if (isRightSubTree) {
                    parent.right = node;
                    isRightSubTree = false;
                }else {
                    parent.left = node;
                }
            }
            //进栈(整体数组和父结点的值)
            stack.push(new Entry<>(arrPointer, node));
            arrPointer = subarray;
            //如果subarray为空数组,证明没有左子树了,跳出while循环
            if (subarray.length == 0) {
                break;
            }
        }
        if (!stack.isEmpty()) {
            Entry<int[],TreeNode> childrenEntry = stack.peek();
            //如果数组长度为1,则该结点为叶子结点,直接弹栈
            //或者:如果此时isRightSubTree也是true,证明本来要去找右子树的,结果没找到,这个值没有被修改
            //这就代表:当前结点已经构建完毕
            boolean childrenIsLeaf = childrenEntry.getKey().length == 1;
            if (childrenIsLeaf || isRightSubTree) {
                stack.pop();
                //如果此时二叉树已经遍历完毕,并且栈内只剩下一个元素,直接返回
                if (preValueIndex == in.length && stack.size() == 1) {
                    return stack.pop().getValue();
                }
            }
            Entry<int[],TreeNode> parentEntry = stack.peek();
            //如果当前的孩子结点是父结点的左孩子,则用父结点的value取索引;右孩子则用孩子结点value取索引
            boolean childrenIsRight = parentEntry.getValue().right == childrenEntry.getValue();
            //这个地方到底使用父结点的value还是子结点的value,要取决于当前子结点是否为右孩子
            int thisNodeValueIndex = ArrayUtils.indexOf(parentEntry.getKey(), 
                    (childrenIsRight ? childrenEntry : parentEntry).getValue().val);
            int[] rightSubTree = ArrayUtils.subarray(parentEntry.getKey(), 
                    thisNodeValueIndex + 1, parentEntry.getKey().length);
            arrPointer = rightSubTree;
            isRightSubTree = true;
        }
    }
    
    return root;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

LinkedBear的个人空间

0 篇文章14 人订阅

相关文章

来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

28450
来自专栏Android机动车

数据结构学习笔记——树(上)

之前一直介绍的是一对一的线性结构,可现实中还有多一对多的情况需要处理,这就是今天要介绍的一对多的数据结构——树。

9220
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

21850
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

9530
来自专栏F_Alex

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

11620
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

31550
来自专栏编程坑太多

HashMap 源码解析

13120
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

8120
来自专栏calmound

110Balanced Binary Tree

问题:判断二叉树是否为平衡二叉树 分析:树上的任意结点的左右子树高度差不超过1,则为平衡二叉树。          搜索递归,记录i结点的左子树高度h1和右子树...

29660
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

21280

扫码关注云+社区

领取腾讯云代金券