java由先序、后序序列构造二叉树

Love The Way You Lie 2022-04-10 03:44 165阅读 0赞

一道经典面试题：

--------------------

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

--------------------

解题思路（重要）：

先来分析一下前序遍历和中序遍历得到的结果，

前序遍历第一位是根节点；   
中序遍历中，根节点左边的是根节点的左子树，右边是根节点的右子树。

例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}。

首先，根节点 是\{ 1 \}；   
左子树是：前序\{ 2,4,7 \} ，中序\{ 4,7,2 \}；   
右子树是：前序\{ 3,5,6,8 \} ，中序\{ 5,3,8,6 \}；

这时，如果我们把左子树和右子树分别作为新的二叉树，则可以求出其根节点，左子树和右子树。

这样，一直用这个方式，就可以实现重建二叉树。

也就是把第一步所的到的前序\{ 2,4,7 \} ，中序\{ 4,7,2 \}再看成一个二叉树让它接着拆分成新的二叉树。

超精简，短小精悍的代码：

public class PreAndIn {
        private static int pre[];
        private static int in[];
    
        public static BinaryNode<Integer> create(int preStart, int preEnd, int inStart, int inEnd) {
            //构造父节点，再根据先根序列找到中根序列中根的位置
            BinaryNode<Integer> root = new BinaryNode<Integer>(pre[preStart]);
            int i=inStart;
            while(in[i] != root.data)
                i++;
    
            //找到中根序列中根的索引i后，构造左子树、右子树。
            if (i != inStart) {
                root.left = create(preStart + 1, preStart + i - inStart, inStart, i - 1);//此处需要万分注意的就是，先根、后根序列的起始位置，可以用debug模式一步步运行来体会这么写的好处。
            }
            if (i != inEnd) {
                root.right = create(preStart + i + 1 - inStart, preEnd, i + 1, inEnd);
            }
            return root;
        }
    
        public static BinaryNode<Integer> manage() {
           return create(0,pre.length-1,0,pre.length-1);
        }
    
        public static void main(String args[]) {
            pre = new int[]{1,2,4,7,3,5,6,8};
            in = new int[]{4,7,2,1,5,3,8,6};
            System.out.println(manage().left);
        }
    }

manage方法返回的就是一颗完整的树的根节点，我们可以通过输出左右节点的值来检查结果的正确性~~