根据前序与中序重构二叉树

时间:2021-02-20 17:30:22
问题描述:输入某二叉树的中序和前序(后序)遍历结果,请重构出该二叉树。
首先,我们需要回顾二叉树的三种遍历方式:
前序遍历:根+左子树+右子树
中序遍历:左子树+根+右子树
后序遍历:左子树+右子树+根

假设,当前二叉树的前序遍历结果为{1,2,4,5,3,6},中序遍历结果为{4,2,5,1,3,6}

我们首先尝试分步构造:

1.前序遍历的第一个元素,必然是树根,此处为1。

  那么我们可以构造出如下图所示的二叉树:

   根据前序与中序重构二叉树

  

2.根据“1”在中序出现的位置,将中序遍历的结果分成左右两棵子树,它们的中序遍历分别是:
  {4,2,5} 和{3,6};这两棵子树的前序结果:{2,4,5}和{3,6}。


3.现在我们重复步骤1、2,构造左子树,如下图所示:


根据前序与中序重构二叉树

4.现在我们重复步骤1、2,构造右子树,如下图所示:


根据前序与中序重构二叉树


5.合并树节点得到最终结果:


 根据前序与中序重构二叉树


结合以上步骤,我们可以总结出如下规律:

1.根据前序(后序也适用)遍历结果,找到树根,设为ROOT,并生成一个以ROOT为根节点,左右子树

都为NULL的树

2.根据ROOT在中序遍历中的索引,将中序遍历结果分为:左子树,右子树;同时我们也要明确左右子树

对应的前序(后序)遍历结果

3.递归的执行步骤1和2即可构造出唯一的二叉树。


关于二叉树的定义,这里就不给出了,下面提供了根据中序和前序遍历结果重构二叉树的关键代码(Java实现):

[java]  view plain  copy
  1. /** 
  2.      * 根据前序和中序遍历数组重构二叉树 
  3.      * @param preOrder:前序遍历数组 
  4.      * @param inOrder:中序遍历数组 
  5.      * @return root:二叉树 
  6.      */  
  7.     static BinaryTree reBuildBinaryTree(Object[] preOrder,Object[] inOrder){  
  8.   
  9.         //递归退出条件  
  10.         if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0) {  
  11.             return null;  
  12.         }  
  13.         // 前序遍历的结果的第一个元素即为二叉树的根节点  
  14.         BinaryTree root=new BinaryTree(preOrder[0]);  
  15.           
  16.         //根节点在中序遍历中的索引  
  17.         int i=0;  
  18.         // 获取根节点在中序遍历中的索引  
  19.         for (;i < inOrder.length;i++) {  
  20.             if (inOrder[i] == preOrder[0]) {  
  21.                 break;  
  22.             }  
  23.         }  
  24.           
  25.         //构造左子树的前序和中序数组  
  26.         Object[] leftPre = Arrays.copyOfRange(preOrder, 1, i + 1);  
  27.         Object[] leftIn = Arrays.copyOfRange(inOrder, 0, i);  
  28.           
  29.         //构造右子树的前序和中序数组  
  30.         Object[] rightPre = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);  
  31.         Object[] rightIn = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);  
  32.           
  33.         //递归构建当前根节点的左子树  
  34.         root.left = reBuildBinaryTree(leftPre, leftIn);  
  35.           
  36.         //递归构建当前根节点的右子树  
  37.         root.right = reBuildBinaryTree(rightPre, rightIn);  
  38.           
  39.         //递归构建二叉树完成, 返回根节点  
  40.         return root;  
  41.     }  

扩展思考:

根据前序与后序结果,可以重构出唯一的二叉树吗?

答案是不一定。

证明如下:

情况一:假设前序结果是{3,1,2},后序结果是{2,1,3}

那么二叉树的结构可能如下:

     3
    / 
   1
  /
 2
   
   3
    \
     1
      \
       2

这种情况下,二叉树并不唯一;


情况二:假设前序结果是{3,1,2},后序结果是{1,2,3}

那么二叉树的结构如下:

     3
    /  \
   1   2