【题7 重建二叉树】Java实现

约定不等于承诺〃 2022-03-30 06:55 132阅读 0赞

**【题目7 重建二叉树】**  
**【题目】**  
输入某二叉树的前序遍历和 中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。  
例如，输入前序遍历\{1，2，4，7，3，5，6，8\}，和中序遍历\{4，7，2，1，5，3，8，6\}，则重建如图所示的二叉树并输出它的头节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
前序遍历中，第一个数字总是树的根节点的值，但在中序遍历中，根结点的值在序列中间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]

package ti6;
    
    public class No6ReConstructBinaryTree {
        public static void main(String[] args) {
            int[] preOrder={1,2,4,7,3,5,6,8};
            int[] inOrder={4,7,2,1,5,3,8,6};
            BinaryTreeNode node=reConstruct(preOrder,inOrder);
            printTree(node);
        }
        //二叉树节点
        public static class BinaryTreeNode{
            int value;
            BinaryTreeNode left;
            BinaryTreeNode right;
        }
        
        /**
         * 判断输入合法性
         * @param preOrder
         * @param inOrder
         * @return
         */
        public static BinaryTreeNode reConstruct(int[] preOrder,int[] inOrder){
            if(preOrder==null||inOrder==null||preOrder.length!=inOrder.length||preOrder.length<1)
                return null;
            return construct(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
        }
        
        /**
         * 根据前序遍历和中序遍历构建二叉树
         * @param preOrder    前序遍历序列
         * @param ps        前序遍历开始位置
         * @param pe        前序遍历结束位置
         * @param inOrder    中序遍历序列
         * @param is        中序遍历开始位置
         * @param ie        中序遍历结束位置
         * @return            构建的树的根节点
         */
        public static BinaryTreeNode construct(int[] preOrder,int ps,int pe,int[] inOrder,int is,int ie){
            //开始位置大于结束位置说明已经处理到叶节点了
            if(ps>pe)
                return null;
            ///前序遍历第一个数字为当前的根节点
            int value=preOrder[ps];
            //index为根节点在中序遍历序列中的索引
            int index=is;
            while(index<=ie&&inOrder[index]!=value){
                index++;
            }
            System.out.println("当前各参数的数值为->ps:"+ps+" pe:"+pe+" is："+is+" ie："+ie+" index："+index+" rootValue："+value);
            //如果在整个中序遍历中没有找到根节点说明输入的数据是不合法的
            if(index>ie){
                throw new RuntimeException("invalid input"+index);
            }
            BinaryTreeNode node=new BinaryTreeNode();
            node.value=value;
            //当前节点的左子树的个数为index-is
            //左子树对应的前序遍历的位置在preOrder[ps+1,ps+index-is]
            //左子树对应的中序遍历的位置在inOrder[is,index-1]
            node.left=construct(preOrder,ps+1,ps+index-is,inOrder,is,index-1);
            //当前节点的右子树的个数为ie-index
            //右子树对应的前序遍历位置在preOrder[ps+index-is+1,pe]
            //右子树对应的中序遍历位置在inOrder[index+1,ie]
            node.right=construct(preOrder,ps+index-is+1,pe,inOrder,index+1,ie);
            return node;
        }
        //中序遍历递归打印
        public static void printTree(BinaryTreeNode node){
            if(node!=null){
                printTree(node.left);
                System.out.print(node.value+" ");
                printTree(node.right);
            }
        }
        
    }

二叉树三种遍历：  
**前序遍历，中序遍历，后序遍历。实现：递归和循环两种方法**  
面试题26 树的子结构  
面试题34二叉树中和为某一值的路径  
面试题55二叉树的深度  
面试题7重建二叉树  
面试题33二叉搜索树的后序遍历序列  
（应该对2\*3=6中实现方法了如指掌）  
**宽度优先遍历**  
面试题32 从上到下打印二叉树  
**二叉树特例：**  
**1. 二叉搜索树：**  
左子节点总是 小于或等于根结点，右子节点总是大于或等于根结点  
面试题36 二叉搜索树与双向链表  
面试题68 树中两节点的最低公共祖先  
**2堆**  
（1）最大堆：根结点值最大  
（2）最小堆：根结点值最小  
**3红黑树**  
树中的节点定义为红、黑两种颜色，通过规则确保从根结点到叶节点的最长路径的长度不超过最短路径的两倍。  
面试题40 最小的k个数

参考：  
1.《剑指offer》  
2.[https://www.cnblogs.com/gl-developer/p/6444280.html][https_www.cnblogs.com_gl-developer_p_6444280.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220330/7e7ff903f06548aea5a6f2494c10ce06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220330/b2f80734e0ee4dc5ba351e646d5bbb50.png
[https_www.cnblogs.com_gl-developer_p_6444280.html]: https://www.cnblogs.com/gl-developer/p/6444280.html