轉(zhuǎn)自官方題解

如何遍歷一棵樹(shù)

有兩種通用的遍歷樹(shù)的策略：

寬度優(yōu)先搜索（BFS）

我們按照高度順序一層一層的訪問(wèn)整棵樹(shù)，高層次的節(jié)點(diǎn)將會(huì)比低層次的節(jié)點(diǎn)先被訪問(wèn)到。
深度優(yōu)先搜索（DFS）

在這個(gè)策略中，我們采用深度作為優(yōu)先級(jí)，以便從跟開(kāi)始一直到達(dá)某個(gè)確定的葉子，然后再返回根到達(dá)另一個(gè)分支深度優(yōu)先搜索策略又可以根據(jù)根節(jié)點(diǎn)、左孩子和右孩子的相對(duì)順序被細(xì)分為前序遍歷，中序遍歷和后序遍歷。

下圖中的頂點(diǎn)按照訪問(wèn)的順序編號(hào)，按照 1-2-3-4-5 的順序來(lái)比較不同的策略。

本問(wèn)題就是從前序和中序遍歷序列構(gòu)造對(duì)應(yīng)的二叉樹(shù)。

方法 1：遞歸

結(jié)構(gòu)定義

首先，定義樹(shù)的存儲(chǔ)結(jié)構(gòu) TreeNode 。

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

算法

如上文所提到的，先序遍歷的順序是 Root -> Left -> Right，這就能方便的從根開(kāi)始構(gòu)造一棵樹(shù)。

首先，preorder 中的第一個(gè)元素一定是樹(shù)的根，這個(gè)根又將 inorder 序列分成了左右兩棵子樹(shù)?，F(xiàn)在我們只需要將先序遍歷的數(shù)組中刪除根元素，然后重復(fù)上面的過(guò)程處理左右兩棵子樹(shù)。

class Solution {
    // start from first preorder element
    int pre_idx = 0;
    int[] preorder;
    int[] inorder;
    HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

    public TreeNode helper(int in_left, int in_right) {
        // if there is no elements to construct subtrees
        if (in_left == in_right)
            return null;

        // pick up pre_idx element as a root
        int root_val = preorder[pre_idx];
        TreeNode root = new TreeNode(root_val);

        // root splits inorder list
        // into left and right subtrees
        int index = idx_map.get(root_val);

        // recursion 
        pre_idx++;
        // build left subtree
        root.left = helper(in_left, index);
        // build right subtree
        root.right = helper(index + 1, in_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;

        // build a hashmap value -> its index
        int idx = 0;
        for (Integer val : inorder)
            idx_map.put(val, idx++);
        return helper(0, inorder.length);
    }
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O( n ),我們用主定理來(lái)計(jì)算時(shí)間復(fù)雜度：

$T(N)=aT(\frac{N}b)+\Theta(N^u0z1t8os)$

這個(gè)方程表示在 $\Theta(N^u0z1t8os)$ 的時(shí)間內(nèi)將問(wèn)題分成 $a$ 個(gè)大小為 $\frac{N}b$ 的子問(wèn)題解決。

當(dāng)前將問(wèn)題分解成了兩個(gè)子問(wèn)題 a = 2，每個(gè)子問(wèn)題（計(jì)算左右兩棵子樹(shù)）的大小是原始問(wèn)題的一般 b = 2，同時(shí)劃分只需要常數(shù)的時(shí)間 d = 0。

這意味著 $log_b(a) > b$ ，因此適用于主定理的第一種情況，時(shí)間復(fù)雜度為 $O(N^{log_b(a)}) = O(N)$ 。

空間復(fù)雜度：O( n ),存儲(chǔ)整棵樹(shù)的開(kāi)銷(xiāo)。