剑指 Offer 07. 重建二叉树

递归

class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        if(preorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        // 问题一：找根结点的位置，通过 HashMap 解决。
        int idx = 0;
        for(; idx < inorder.length; idx++){
    
            if(inorder[idx] == preorder[0]) break;
        }
        // 问题二：java 数组不能获取子数组，通过拷贝或索引解决。
        if(idx >= 0){
    
            root.left = this.buildTree(Arrays.copyOfRange(preorder, 1, idx + 1), Arrays.copyOfRange(inorder, 0, idx));
        }
        if(idx <= preorder.length - 1){
    
            root.right = this.buildTree(Arrays.copyOfRange(preorder, idx + 1, preorder.length), Arrays.copyOfRange(inorder, idx + 1, inorder.length));         
        }
        return root;
    }
}

	根节点前序索引	中序左边界	中序右边界
左子树	rootidx + 1	left	i - 1
右子树	rootidx + i - left + 1	i + 1	right

TIPS： i - left + rootidx + 1 含义为 根节点索引 + 左子树长度 + 1

class Solution {
    
    HashMap<Integer, Integer> d = new HashMap<>(); // 类变量
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        // 中序中根结点分割左右子树 [left, idx), (idx, right)
        // 方便获取根结点的位置
        for(int i = 0; i < inorder.length; i++)
            d.put(inorder[i], i); 
        // rootidx = 0, left = 0, right = inorder.length - 1
        return recur(preorder, 0, 0, inorder.length - 1);
    }
	// 根结点索引在 preorder 中计算，范围在 inorder 中计算。
    TreeNode recur(int[] preorder, int ridx, int left, int right) {
    
        if(left > right) return null;  // 递归终止
        TreeNode node = new TreeNode(preorder[ridx]); // 建立根节点
        int i = d.get(preorder[ridx]); // 根节点划分左右子树
        node.left = recur(preorder, ridx + 1, left, i - 1); // 开启左子树递归
        node.right = recur(preorder, ridx + i - left + 1, i + 1, right); // 开启右子树递归
        return node;  
    }
}

迭代

class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        int n = preorder.length, idx = 0; // inorder 索引
        if(preorder == null || n == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> q = new ArrayDeque<>();        
        q.push(root);
        
        for(int i = 1; i < n; i++){
     // 遍历 preorder
            int val = preorder[i]; // 前序值
            TreeNode top = q.peek();
            if(top.val != inorder[idx]){
     // 构造左结点
                top.left = new TreeNode(val);
                q.push(top.left);
            } else {
    
                while(!q.isEmpty() && q.peek().val == inorder[idx]){
    
                    top = q.pop();
                    idx++; // 遍历 inorder
                }
                top.right = new TreeNode(val);  // 构造右结点
                q.push(top.right);
            }
        }
        return root;
    }
}