dfs-重建二叉樹-JZ4

描述

給定某二叉樹的前序周遊和中序周遊，請重建出該二叉樹并傳回它的頭結點。

例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建出如下圖所示。

提示:

1.0 <= pre.length <= 2000

2.vin.length == pre.length

3.-10000 <= pre[i], vin[i] <= 10000

4.pre 和 vin 均無重複元素

5.vin出現的元素均出現在 pre裡

6.隻需要傳回根結點，系統會自動輸出整顆樹做答案對比

示例1

輸入： [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

傳回值：{1,2,3,4,#,5,6,#,7,#,#,8}

說明： 傳回根節點，系統會輸出整顆二叉樹對比結果

示例2

輸入： [1],[1]

傳回值： {1}

示例3

輸入： [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

傳回值： {1,2,5,3,4,6,7}

思路：

前序周遊和中序周遊，重建二叉樹，主要應用dfs與遞歸

• 前序周遊的首元素就是目前遞歸層次的根節點
• 确定左右子樹的範圍，從中間向兩邊查找跟節點索引，從中序周遊中根據根節點的值找到中序周遊數組中根節點的索引
• 目前根節點的左子節點為左子樹的跟節點，拼接、建構二叉樹即可

時間複雜度 O(N)：遞歸了每個結點，N為結點數

空間複雜度 O(N)：遞歸所用的棧空間

代碼

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre == null || pre.length == 0 
            || in == null || in.length == 0 
            || pre.length != in.length) {
            return null;
        }
        return buildBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
    }
    
    private TreeNode buildBinaryTree(int [] pre, int beginPre, int endPre, 
                                     int [] in, int beginIn, int endIn) {
        if (beginPre > endPre || beginIn > endIn) {
            return null;
        }
        int val = pre[beginPre];
        int rootValIn = beginIn;
        while (rootValIn <= endIn) {
            if (in[rootValIn] == val) {
                break;
            }
            rootValIn++;
        }
        TreeNode root = new TreeNode(val);
        //左子樹長度
        int leftLength = rootValIn - beginIn;
        //右子樹長度
        int rightLength = endIn - rootValIn;
        root.left = buildBinaryTree(pre, beginPre+1, beginPre + leftLength, 
                                    in, beginIn, rootValIn-1);
        root.right = buildBinaryTree(pre, endPre - rightLength + 1, endPre, 
                                    in, rootValIn+1, endIn);
        return root;
    }
}