重建二叉树（剑指offer 07）

重建二叉树（剑指offer 07）

目录

一、题目描述

二、思路讲解

三、Java代码实现

四、代码优化

        1、用HashMap来保存中序数组 

        2、将前序遍历数组拿到方法外面 

---

 

一、题目描述

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2: 

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

限制：

0 <= 节点个数 <= 5000

二、思路讲解

        根据二叉树的遍历知识我们可以知道，前序遍历的第一个节点为根节点；中序遍历中，根节点左边所有的节点在它的左子树中，右边所有的节点在它的右子树中。也就是说，前序遍历数组和后序遍历数组可以分成这样的结构：

        前序遍历数组： | 根节点 | 左子树 | 右子树 |

        中序遍历数组：        | 左子树 | 根节点 | 右子树 | 

        前序遍历中，根节点右边的节点就是左子树的根节点，而我们可以在中序遍历中找到左子树的长度left_len，那么，在前序遍历数组中距离根节点left_len的节点就是右子树的根节点。

        我们就可以根据这个思路遍历树中所有的节点。

三、Java代码实现

class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return fun(0, inorder.length-1, 0, preorder, inorder);
    }

    
    public static TreeNode fun(int left, int right, int index,
                                int[] preorder, int[] inorder){

        //越过了叶子节点
        if(left>right){
            return null;
        }

        //构造树
        TreeNode root = new TreeNode(preorder[index]);

        int i;
        
        //在中序数组上找到当前节点。当前节点左边为左子树，右边为右子树
        for(i=0; i 
 
四、代码优化 
        1、用HashMap来保存中序数组  
        因为每次遍历时都要用一个循环去中序数组中找当前节点，那么我们用一个HashMap来保存中序数组中的所有节点，这样再找时，时间复杂度为O(1)。虽然会提升一点空间复杂度，但是大大降低了时间复杂度。
 
 
        2、将前序遍历数组拿到方法外面  
        这样就不需要每次递归的时候都传入了，也能降低空间复杂度。
 
 
class Solution {
    
    private static int[] preorder;
    //用来保存inorder，使查找的速度加快
    private static HashMap map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        this.preorder = preorder;

        for(int i=0; iright){
            return null;
        }

        //构造树
        TreeNode root = new TreeNode(preorder[index]);

        //在中序数组上找到当前节点。当前节点左边为左子树，右边为右子树
        int i = map.get(preorder[index]);

        //构建当前节点的左子树
        root.left = fun(left, i-1, index+1);
        //构建当前节点的右子树
        root.right = fun(i+1, right, index+i-left+1);

        return root;
    }
}
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5687442.html