亲宝软件园·资讯

展开

剑指Offer对答如流系列 - 重建二叉树

沉晓Jeffery 人气:2

面试题6:重建二叉树

题目描述:

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。二叉树结点的定义如下:

class Node{
    int e;
    Node left;
    Node right;
    Node(int x) { e = x; }
}

这道题主要测试你对二叉树性质的了解,非常有代表性,不过在这之前,我们先把二叉树的基本性质捋一遍。

二叉树的基本性质

(1)关于树

树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。

树的基本术语有:

  • 每个结点有零个或多个子结点
  • 没有父节点的结点称为根节点
  • 每一个非根结点有且只有一个父节点
  • 除了根结点外,每个子结点可以分为多个不相交的子树。
  • 若一个结点有子树,那么该结点称为子树根的“双亲”,子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”
  • 一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
  • 结点的度:结点拥有的子树的数目
  • 叶子结点:度为0的结点
  • 分支结点:度不为0的结点
  • 树的度:树中结点的最大的度
  • 层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1
  • 树的高度:树中结点的最大层次
  • 森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。

“树”是计算机科学中非常重要的一部分内容,它的变形和应用非常之多。比如说,在做通讯录的时候,Android 工程师往往喜欢用字典树来存取数据,对于Java后端,有的时候我们处理的数据的时候也需要进行区间的查询,比如说去年你的博客在什么时间段关注你的人增长最快啊,一天中自己的博文阅读量最高的时间段啊,可以采用线段树来实现。在JDK1.8的HashMap的结构中,当元素超过8个的时候,会转为红黑树等等。

不过对于Java开发而言,二叉树是基础也是接触较多的一种结构。

(2)关于二叉树

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态:

1)空树;

2)只有根的树,即单结点;

3)有根且有一个左子树;

4)有根且有一个右子树;

5)有根且有一个左子树,有一个右子树。

二叉树的性质有:

  • 二叉树第i层上的结点数目最多为2i-1(i>=1)
  • 深度为k的二叉树至多有2k-1个结点(k>=1)
  • 包含n个结点的二叉树的高度至少为(log2n)+1
  • 在任意一棵二叉树中,若叶子结点的个数为n0,度为2的结点数为n2,则n0=n2+1

    第四条的证明: 因为二叉树中所有结点的度数均不大于2,设n0表示度为0的结点个数,n1表示度为1的结点个数,n2表示度为2的结点个数。
    三类结点加起来为总结点个数,于是便可得到:n=n0+n1+n2 (公式1)
    由度之间的关系可得第二个等式:n=n0*0+n1*1+n2*2+1 即n=n1+2n2+1 (公式2)
    将(公式1)(公式2)组合在一起可得到n0=n2+1

了解这第四条性质就差不多了。如果想进一步学习二叉树的性质,不妨去找本《离散数学》?

对二叉树遍历的理解

以这棵树为例:

前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)

    //前序遍历以node为根
    public void preOrder(Node node) {
        //终止条件
        if(node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

这棵树的前序遍历为:FCADBEHGM

中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)

    //中序以node为根的
    public void inOrder(Node node) {
        //终止条件
        if(node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

这棵树的中序遍历为:ACBDFHEMG

后序遍历:左子树 —> 右子树 —> 根结点(最后遍历根节点)

        //中序以node为根
        public void postOrder(Node node) {
            //终止条件
            if(node == null) {
                return;
            }
    
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }

这棵树的后序遍历为:ABDCHMGEF

层序遍历:

    //层序遍历
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while( !q.isEmpty() ) {
            Node cur = q.remove();
            System.out.println(cur.e);
            
            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.right);  //后出
        }
    }

这棵树层序遍历为:FCEADHGBM

所谓的前序、中序、后序,就是对根节点而言的,左右的遍历顺序不变,前序就是根节点最先遍历,然后左右;中序就是把根节点放在中间遍历;后序则是把根节点放在最后遍历。

中序遍历能够帮助我们很好地确定根节点的位置,这个就有点可怕了,实际面试的时候,不单单会有给出前序遍历和中序遍历的结果让你重建二叉树,还有给出后序遍历和中序遍历结果或者 层序遍历和中序遍历的结果重建二叉树、

其他的遍历组合均不能还原出二叉树的形状,因为无法确认其左右孩子。例如,前序为AB,后序为AB,则无法确认出,B节点是A节点的左孩子还是右孩子,因此无法还原。

题解

思路:通过前序遍历获得根节点的位置,利用根节点将中序序列分为左子树和右子树,然后不断的递归划分即可。

代码中有解释。

  private Node buildTree(int[] pre, int preBegin, int preEnd, int[] mid, int midBegin, int midEnd) {
        // 前序遍历确第一个元素为根节点
        Node root = new Node(pre[preBegin]);
        // 用于标记中序遍历结果中根节点的位置
        int midRootLocation= 0;
        for (int i = midBegin; i <= midEnd; i++) {
            if (mid[i] == pre[preBegin]) {  
                midRootLocation= i;
                break;
            }
        }

        if ( midRootLocation - midBegin >= 1 ) {
            // 递归得到左子树
            
            // 中序遍历:左子树—> 根结点 —> 右子树(在中间遍历根节点)
            // midRootLocation标记了中序遍历结果中根节点的位置,这个位置两端对应根节点左子树和右子树
            // midRootLocation- midBegin 表示该根节点左边的节点的数量
            
            // 前序遍历:根结点 —> 左子树 —> 右子树(先遍历根节点,然后左右)
            // preBegin 标记了前序遍历结果中根节点的位置
            // preBegin + 1 表示该根节点左子树起始位置
            // preBegin + (midRootLocation- midBegin) 表示给根节点左子树结束的位置
            Node left = buildTree(pre, preBegin + 1, preBegin + (midRootLocation- midBegin),
                    mid, midBegin, midRootLocation - 1);
            root.left = left;
        }


        if ( midEnd - midRootLocation >= 1 ) {
            // 递归得到右子树
            // 原理和上面相同
            Node right = buildTree(pre, preEnd - (midEnd - midRootLocation) + 1, preEnd,
                    mid, midRootLocation+ 1, midEnd);
            root.right = right;
        }

        return root;
    }

举一反三

(1)给出后序遍历和中序遍历的结果重建二叉树

思路:通过后序获取根节点的位置,然后在中序中划分左子树和右子树,然后递归划分即可。

形式与上面 给出 前序遍历和中序遍历的结果重建二叉树相同

    private Node buildTree(int[] mid, int midBegin, int midEnd, int[] end, int endBegin, int endEnd) {
        
        Node root = new Node(end[endEnd]);
        int midRootLocation = 0;
        for (int i = midEnd; i >= midBegin; i--) {
            if (mid[i] == end[endEnd]) {
                midRootLocation = i;
                break;
            }
        }
        
        //还原左子树
        if (midRootLocation - midBegin >= 1 ) {
            Node left = buildTree(mid, midBegin, midRootLocation - 1, end, endBegin, endBegin + (midRootLocation - midBegin) - 1);
            root.left = left;
        }

        //还原右子树
        if (midEnd - midRootLocation >=  1 ) {
            Node right = buildTree(mid, midRootLocation + 1, midEnd, end, endEnd - (midEnd - midRootLocation), endEnd - 1);
            root.right = right;
        }
        
        return root;
    }

(2)给出层序遍历和中序遍历结果重建二叉树

思路:

(1)根据层序遍历获取根节点的位置

(2)根据(1)将中序划分为左子树和右子树

(3)根据(2)划分出的左子树和右子树分别在层序遍历中获取其对应的层序顺序

(4)然后递归调用划分。

  private Node buildTree(int[] mid, int[] level, int midBegin, int midEnd) {

        // 层序遍历的第一个结果是 根节点
        Node root = new Node(level[0]);
        // 用于标记中序遍历的根节点
        int midLocation = -1;
        for (int i = midBegin; i <= midEnd; i++) {
            if (mid[i] == level[0]) {
                midLocation = i;
                break;
            }
        }

        if (level.length >= 2) {
            if (isLeft(mid, level[0], level[1])) {
                Node left = buildTree(mid, getLevelArray(mid, midBegin, midLocation - 1, level), midBegin, midLocation - 1);
                root.left = left;
                if (level.length >= 3 && !isLeft(mid, level[0], level[2])) {
                    Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
                    root.right = right;
                }
            } else {
                Node right = buildTree(mid, getLevelArray(mid, midLocation + 1, midEnd, level), midLocation + 1, midEnd);
                root.right = right;
            }
        }
        return root;
    }


    // 功能 : 判断元素是根节点的左子树节点还是右子树节点
    // 参数 : target为根节点 isLeft在中序遍历结果中判断children是根节点的左子树还是右子树
    // 返回值 : 如果为左子树节点则为true 否则为false
    private boolean isLeft(int[] array, int target, int children) {
        boolean findC = false;

        for (int temp : array) {
            if (temp == children) {
                findC = true;
            } else if (temp == target) {
                return findC;
            }
        }
        return false;
    }


    // 功能: 将中序序列中midBegin与midEnd的元素依次从level中提取出来,保持level中的元素顺序不变
    private int[] getLevelArray(int[] mid, int midBegin, int midEnd, int[] level) {
        int[] result = new int[midEnd - midBegin + 1];
        int curLocation = 0;
        for (int i = 0; i < level.length; i++) {
            if (contains(mid, level[i], midBegin, midEnd)) {
                result[curLocation++] = level[i];
            }
        }
        return result;
    }

    // 如果array的begin和end位置之间(包括begin和end)含有target,则返回true。
    private boolean contains(int[] array, int target, int begin, int end) {
        for (int i = begin; i <= end; i++) {
            if (array[i] == target) {
                return true;
            }
        }
        return false;
    }

加载全部内容

相关教程
猜你喜欢
用户评论