一、题目描述

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

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

示例 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代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {

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

    /**
        left:   左子树在inorder上的左边界
        right： 右子树的inorder上的右边界
        index： 当前节点在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<inorder.length; i++){
            if(inorder[i] == preorder[index]){
                break;
            }
        }

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

        return root;
    }
}

四、代码优化

1、用HashMap来保存中序数组

因为每次遍历时都要用一个循环去中序数组中找当前节点，那么我们用一个HashMap来保存中序数组中的所有节点，这样再找时，时间复杂度为O(1)。虽然会提升一点空间复杂度，但是大大降低了时间复杂度。

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

这样就不需要每次递归的时候都传入了，也能降低空间复杂度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private static int[] preorder;
    //用来保存inorder，使查找的速度加快
    private static HashMap<Integer, Integer> map = new HashMap<>();

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

        this.preorder = preorder;

        for(int i=0; i<inorder.length; i++){
            map.put(inorder[i], i);
        }

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

    /**
        left:   左子树在inorder上的左边界
        right： 右子树的inorder上的右边界
        index： 当前节点在inorder上的索引
     */
    public static TreeNode fun(int left, int right, int index){

        //越过了叶子节点
        if(left>right){
            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;
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125067.html