樹的基礎知識

樹是算法面試經常遇到的數(shù)據結構之一，在實際工作中也有可能經常用到……

應聘者在準備算法面試時最需要重視的是二叉樹……

二叉樹是一種典型的具有遞歸性質的數(shù)據結構。二叉樹的根節(jié)點可能有子節(jié)點，子節(jié)點又是對應子樹的根節(jié)點，它可能也有自己的子節(jié)點。這就類似于 “子又生孫，孫又生子，子子孫孫無窮盡也”。由于二叉樹本身就是遞歸的數(shù)據結構，因此很多與二叉樹相關的面試題用遞歸的代碼解決就很直觀

……

二叉樹的深度優(yōu)先搜索

與二叉樹相關的面試題絕大部分都是為了考查二叉樹的遍歷。第 7 章介紹了二叉樹的廣度優(yōu)先搜索，本節(jié)將深入探討二叉樹的深度優(yōu)先搜索及典型的面試題。二叉樹的深度優(yōu)先搜索可以細分為中序遍歷、前序遍歷和后序遍歷

中序遍歷

……

第一，遞歸有其固有的局限性。如果二叉樹的深度（從根節(jié)點到葉節(jié)點的最長路徑的長度）太大，那么遞歸的代碼可能會導致調用棧溢出的問題。第二，遞歸的代碼實在過于簡單，面試官也希望增加面試的難度，因此在面試的時候經常會限制編寫遞歸的中序遍歷的代碼

把遞歸代碼改寫成迭代的代碼通常需要用到棧，改寫中序遍歷的代碼也不例外……

前序遍歷

……

前序遍歷的遞歸代碼實現(xiàn)和中序遍歷的遞歸代碼實現(xiàn)類似……

前序遍歷的迭代代碼實現(xiàn)和中序遍歷的迭代代碼實現(xiàn)也很類似……

后序遍歷

后序遍歷的遞歸代碼實現(xiàn)和中序遍歷的遞歸代碼實現(xiàn)類似……

和中序遍歷、前序遍歷相比，后序遍歷的迭代代碼要稍微復雜一點。當達到某個節(jié)點時，如果之前還沒有遍歷過它的右子樹就得前往它的右子節(jié)點，如果之前已經遍歷過它的右子樹那么就可以遍歷這個節(jié)點。也就是說，此時要根據它的右子樹此前有沒有遍歷過來確定是否應該遍歷當前的節(jié)點。如果此前右子樹已經遍歷過，那么在右子樹中最后一個遍歷的節(jié)點應該是右子樹的根節(jié)點，也就是當前節(jié)點的右子節(jié)點?？梢?strong>記錄遍歷的前一個節(jié)點。如果一個節(jié)點存在右子節(jié)點并且右子節(jié)點正好是前一個被遍歷的節(jié)點，那么它的右子樹已經遍歷過，現(xiàn)在是時候遍歷當前的節(jié)點了

3 種遍歷方法小節(jié)

下面比較中序遍歷、前序遍歷和后序遍歷這 3 種不同遍歷算法的代碼。它們的遞歸代碼都很簡單，只需要調整代碼的順序就能寫出對應算法的代碼

它們的迭代代碼也很類似，如它們都需要用到一個棧，而且代碼的基本結構很相像，都有兩個 while 循環(huán)并且它們的條件都一樣。需要留意遍歷當前節(jié)點的時機。前序遍歷一邊順著指向左子節(jié)點的指針移動一邊遍歷當前的節(jié)點，而中序遍歷和后序遍歷則順著指向左子節(jié)點的指針移動時只將節(jié)點放入棧中，并不遍歷遇到的節(jié)點。只有當?shù)竭_最左子節(jié)點之后再從棧中取出節(jié)點遍歷。后序遍歷最復雜，還需要保存前一個遍歷的節(jié)點，并根據前一個遍歷的節(jié)點是否為當前節(jié)點的右子節(jié)點來決定此時是否可以遍歷當前的節(jié)點

不管是哪種深度優(yōu)先搜索算法，也不管是遞歸代碼還是迭代代碼，如果二叉樹有 n 個節(jié)點，那么它們的時間復雜度都是 O(n)。如果二叉樹的深度為 h，那么它們的空間復雜度都是 O(h)。在二叉樹中，二叉樹的深度 h 的最小值是 log2(n+1)，最大值為 n……

3 種不同的二叉樹深度優(yōu)先搜索算法都有遞歸和迭代兩種代碼實現(xiàn)。這 6 段我們一定要深刻理解并能熟練寫出正確的代碼。這是因為很多與二叉樹相關的面試題實際上都是在考查二叉樹的深度優(yōu)先搜索，理解中序遍歷、前序遍歷和后序遍歷算法并能熟練寫出代碼，這些面試題都能迎刃而解。請看下面幾個例題

面試題 47：二叉樹剪枝

題目：一棵二叉樹的所有節(jié)點的值要么是 0 要么是 1，請剪除該二叉樹中所有節(jié)點的值全都是 0 的子樹

public static TreeNode pruneTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if (root.left == null && root.right == null && root.val == 0) {
        return null;
    }
    return root;
}

上述代碼實質上是實現(xiàn)了遞歸的后序遍歷。每當遍歷到一個節(jié)點，如果該節(jié)點符合條件，則將該節(jié)點刪除。由于是后序遍歷，因此先對根節(jié)點 root 的左右子樹遞歸調用函數(shù) pruneTree 刪除左右子樹中節(jié)點值全是 0 的子樹。只有當 root 的左右子樹全部為空，并且它自己的值也是 0 時，整個節(jié)點才能被刪除……

面試題 48：序列化和反序列化二叉樹

題目：請設計一個算法將二叉樹序列化成一個字符串，并能將該字符串反序列化出原來二叉樹的算法

……以前序遍歷的順序遍歷二叉樹最適合序列化。如果采用前序遍歷的順序，那么二叉樹的根節(jié)點最先序列化到字符串中，然后是左子樹，最后是右子樹。這樣做的好處是在反序列化時最方便，從字符串中讀出的第 1 個數(shù)值一定是根節(jié)點的值

……盡管 null 節(jié)點通常沒有在圖上畫出來，但它們對樹的結構是至關重要的。因此，應該把 null 節(jié)點序列化成一個特殊的字符串。如果把 null 節(jié)點序列化成 “#”……

public static String serialize(TreeNode root) {
    if (root == null) {
        return "#";
    }
    String leftStr = serialize(root.left);
    String rightStr = serialize(root.right);
    return root.val + "," + leftStr + "," + rightStr;
}

public static TreeNode deserialize(String data) {
    String[] nodeStrs = data.split(",");
    int[] i = {0};
    return dfs(nodeStrs, i);
}

private static TreeNode dfs(String[] strs, int[] i) {
    String str = strs[i[0]];
    i[0]++;
    if (str.equals("#")) {
        return null;
    }
    TreeNode node = new TreeNode(Integer.valueOf(str));
    node.left = dfs(strs, i);
    node.right = dfs(strs, i);
    return node;
}

在上述代碼中，字符串數(shù)組 nodeStrs 保存分隔之后的所有節(jié)點對應的字符串，可以根據數(shù)組中的每個字符串逐一構建二叉樹的每個節(jié)點。遞歸函數(shù) dfs 的每次執(zhí)行都會從字符串數(shù)組中取出一個字符串并以此反序列化出一個節(jié)點（如果取出的字符串是 “#”，則返回 null 節(jié)點）

我們需要一個下標去掃描字符串數(shù)組 nodeStrs 中的每個字符串。通常用一個整數(shù)值來表示數(shù)組的下標，但在上述代碼中卻定義了一個長度為 1 的整數(shù)數(shù)組 i。這是因為遞歸函數(shù) dfs 每反序列化一個節(jié)點時下標就會增加 1，并且函數(shù)的調用者需要知道下標增加了。如果函數(shù) dfs 的第 2 個參數(shù) i 是整數(shù)類型，那么即使在函數(shù)體內修改 i 的值，修改之后的值也不能傳遞給它的調用者。但把 i 定義為整數(shù)數(shù)組之后，可以修改整數(shù)數(shù)組中的數(shù)字，修改之后的數(shù)值就能傳給它的調用者

面試題 49：從根節(jié)點到葉節(jié)點的路徑數(shù)字之和

題目：在一棵二叉樹中所有節(jié)點都在 0~9 的范圍之內，從根節(jié)點到葉節(jié)點的路徑表示一個數(shù)字。求二叉樹中所有路徑表示的數(shù)字之和

基于二叉樹前序遍歷的參考代碼如下所示：

public static int sumNumbers(TreeNode root) {
    return dfs(root, 0);
}

private static int dfs(TreeNode root, int path) {
    if (root == null) {
        return 0;
    }
    path = path * 10 + root.val;
    if (root.left == null && root.right == null) {
        return path;
    }
    return dfs(root.left, path) + dfs(root.right, path);
}

在這個題目中，路徑的定義是從根節(jié)點開始到葉節(jié)點結束，因此上屬代碼中只有遇到葉節(jié)點才返回路徑表示的數(shù)字（代碼中的變量 path）。如果在遇到葉節(jié)點之前就結束路徑，由于不符合題目要求，因此應該返回 0。這是輔助函數(shù) dfs 的第 1 條 if 語句（root==null）為 true 時返回 0 的原因

面試題 50：向下的路徑節(jié)點值之和

題目：給定一棵二叉樹和一個值 sum，求二叉樹中節(jié)點值之和等于 sum 的路徑的數(shù)目。路徑的定義為二叉樹中順著指向子節(jié)點的指針向下移動所經過的節(jié)點，但不一定從根節(jié)點開始，也不一定到葉節(jié)點結束

在這個題目中，二叉樹的路徑的定義發(fā)生了改變，它不一定從根節(jié)點開始，也不一定到葉節(jié)點結束。路徑的起止節(jié)點的不確定性給計算路徑經過的節(jié)點值之和帶來了很大的難度

雖然路徑不一定從根節(jié)點開始，但仍然可以求得從根節(jié)點開始到達當前遍歷節(jié)點的路徑所經過的節(jié)點值之和……

如果在路徑上移動時把所有累加的節(jié)點值之和都保存下來，就容易知道是否存在從任意節(jié)點出發(fā)的值為給定 sum 的路徑……

有了前面的經驗，就可以采用二叉樹深度優(yōu)先搜索來解決與路徑相關的問題。當遍歷到一個節(jié)點時，先累加從根節(jié)點開始的路徑上的節(jié)點值之和，再計算到它的左右子節(jié)點的路徑的節(jié)點值之和。這就是典型的前序遍歷的順序

public static int pathSum(TreeNode root, int sum) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    return dfs(root, sum, map, 0);
}

private static int dfs(TreeNode root, int sum, Map<Integer, Integer> map, int path) {
    if (root == null) {
        return 0;
    }
    path += root.val;
    int count = map.getOrDefault(path - sum, 0);
    map.put(path, map.getOrDefault(path, 0) + 1);
    count += dfs(root.left, sum, map, path);
    count += dfs(root.right, sum, map, path);
    map.put(path, map.get(path) - 1);
    return count;
}

上述代碼用參數(shù) path 表示從根節(jié)點開始的路徑已經累加的節(jié)點值之和，并保存到哈希表 map 中。哈希表的鍵是累加的節(jié)點值之和，哈希表的值是每個節(jié)點值之和出現(xiàn)的次數(shù)。當遍歷到一個節(jié)點時，就把當前節(jié)點的值累加到參數(shù) path。如果這個和之前出現(xiàn)過，則將出現(xiàn)的次數(shù)加 1；如果這個和之前沒有出現(xiàn)過，那么這是它的第 1 次出現(xiàn)。然后更新哈希表 map 保存累加節(jié)點值之和 path 及出現(xiàn)的次數(shù)

輔助函數(shù) dfs 實現(xiàn)了遞歸的前序遍歷，該函數(shù)遍歷到二叉樹的一個節(jié)點時將遞歸地遍歷它的子節(jié)點。因此，當該函數(shù)結束時，程序將回到節(jié)點的父節(jié)點，也就是說，在函數(shù)結束之前需要將當前節(jié)點從路徑中刪除，從根節(jié)點到當前節(jié)點累加的節(jié)點值之和也要從哈希表 map 中刪除。這是在函數(shù) dfs 返回之前更新哈希表 map 把參數(shù) path 出現(xiàn)的次數(shù)減 1 的原因

面試題 51：節(jié)點值之和最大的路徑

題目：在二叉樹中將路徑定義為順著節(jié)點之間的連接從任意一個節(jié)點開始到達任意一個節(jié)點所經過的所有節(jié)點。路徑中至少包含一個節(jié)點，不一定經過二叉樹的根節(jié)點，也不一定經過葉節(jié)點。給定非空的一棵二叉樹，請求出二叉樹所有路徑上節(jié)點值之和的最大值

這個題目中二叉樹路徑的定義又和前面的不同。這里的路徑最主要的特點是路徑有可能同時經過一個節(jié)點的左右子節(jié)點……

……需要先求出左右子樹中路徑節(jié)點值之和的最大值（左右子樹中的路徑不經過當前節(jié)點），再求出經過根節(jié)點的路徑節(jié)點值之和的最大值，最后對三者進行比較得到最大值。由于需要先求出左右子樹的路徑節(jié)點值之和的最大值，再求根節(jié)點，這看起來就是后序遍歷……

public static int maxPathSum(TreeNode root) {
    int[] maxSum = {Integer.MIN_VALUE};
    dfs(root, maxSum);
    return maxSum[0];
}

private static int dfs(TreeNode root, int[] maxSum) {
    if (root == null) {
        return 0;
    }
    int[] maxSumLeft = {Integer.MIN_VALUE};
    int left = Math.max(0, dfs(root.left, maxSumLeft));
    int[] maxSumRight = {Integer.MIN_VALUE};
    int right = Math.max(0, dfs(root.right, maxSumRight));
    maxSum[0] = Math.max(maxSumLeft[0], maxSumRight[0]);
    maxSum[0] = Math.max(maxSum[0], root.val + left + right);
    return root.val + Math.max(left, right);
}

上述代碼按照后序遍歷的順序遍歷二叉樹的每個節(jié)點。由于求左右子樹的路徑節(jié)點值之和的最大值與求整棵二叉樹的路徑節(jié)點值之和的最大值是同一個問題，因此用遞歸的代碼解決這個問題最直觀

代碼中的參數(shù) maxSum 是路徑節(jié)點值之和的最大值。由于遞歸函數(shù) dfs 需要把這個最大值傳給它的調用者，因此參數(shù) maxSum 被定義為長度為 1 的數(shù)組。先遞歸調用函數(shù) dfs 求得左右子樹的路徑節(jié)點值之和的最大值 maxSumLeft 及 maxSumRight，再求出經過當前節(jié)點 root 的路徑的節(jié)點值之和的最大值，那么參數(shù) maxSum 就是這 3 個值的最大值

函數(shù)的返回值是經過當前節(jié)點 root 并前往其左子樹或右子樹的路徑的節(jié)點值之和的最大值。它的父節(jié)點要根據這個返回值求路徑的節(jié)點值之和。由于同時經過左右子樹的路徑不能經過父節(jié)點，因此返回值是變量 left 與 right 的較大值加上當前節(jié)點 root 的值

二叉搜索樹

二叉搜索樹是一類特殊的二叉樹，它的左子節(jié)點總是小于或等于根節(jié)點，而右子節(jié)點總是大于或等于根節(jié)點……

二叉樹的 3 種不同的深度優(yōu)先搜索算法都適用于二叉搜索樹，但中序遍歷是解決二叉搜索樹相關面試題最常用的思路，這是因為中序遍歷按照節(jié)點值遞增的順序遍歷二叉搜索樹的每個節(jié)點……

普通的二叉樹中根據節(jié)點值查找對應的節(jié)點需要遍歷這棵二叉樹，因此需要 O(n) 的時間。但如果是二叉搜索樹就可以根據其特性進行優(yōu)化……如果二叉搜索樹的高度為 h，那么在二叉搜索樹中根據節(jié)點值查找對應節(jié)點的時間復雜度是 O(h)

面試題 52：展平二叉搜索樹

題目：給定一棵二叉搜索樹，請調整節(jié)點的指針使每個節(jié)點都沒有左子節(jié)點。調整之后的樹看起來像一個鏈表，但仍然是二叉搜索樹

看起來需要按照節(jié)點的值遞增的順序遍歷二叉搜索樹中的每個節(jié)點，并將節(jié)點用指向右子節(jié)點的指針連接起來。這就容易讓人聯(lián)想到二叉樹的中序遍歷，只是在這里每遍歷到一個節(jié)點要把前一個節(jié)點的指向右子節(jié)點的指針指向它。基于中序遍歷的參考代碼如下所示：

public static TreeNode increasingBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    TreeNode prev = null;
    TreeNode first = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (prev != null) {
            prev.right = cur;
        } else {
            first = cur;
        }
        prev = cur;
        cur.left = null;
        cur = cur.right;
    }
    return first;
}

上述代碼只是對二叉樹中序遍歷的迭代代碼稍作修改。變量 prev 表示前一個遍歷到的節(jié)點。在遍歷到當前節(jié)點 cur 時，把變量 prev 的右子節(jié)點的指針指向 cur，并將 cur 指向左子節(jié)點的指針設為 null

展平之后的二叉搜索樹的根節(jié)點是值最小的節(jié)點，因此也是中序遍歷第 1 個被遍歷到的節(jié)點。在上述代碼中，變量 first 就是第 1 個被遍歷到的節(jié)點，在展平之后就是二叉搜索樹的根節(jié)點，因此將它作為函數(shù)的返回值

面試題 53：二叉搜索樹的下一個節(jié)點

題目：給定一棵二叉搜索樹和它的一個節(jié)點 p，請找出按中序遍歷的順序該節(jié)點 p 的下一個節(jié)點。假設二叉搜索樹中節(jié)點的值都是唯一的

時間復雜度 O(n) 的解法

解決這個問題的最直觀的思路就是采用二叉樹的中序遍歷……由于中序遍歷會逐一遍歷二叉樹的每個節(jié)點，如果二叉樹有 n 個節(jié)點，那么這種思路的時間復雜度就是 O(n)……棧的空間復雜度為 O(h)，其中 h 為二叉樹的深度

時間復雜度 O(h) 的解法

下面換一個角度來看待二叉搜索樹中節(jié)點 p 的中序遍歷下一個節(jié)點。首先下一個節(jié)點的值一定不會小于節(jié)點 p 的值，而且還是大于或等于節(jié)點 p 的值的所有節(jié)點中值最小的一個……

public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode cur = root;
    TreeNode result = null;
    while (cur != null) {
        if (cur.val > p.val) {
            result = cur;
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return result;
}

如果把二叉樹的深度記為 h，那么該算法的時間復雜度為 O(h)。同時，上述代碼除幾個變量外沒有其他內存開銷，因此空間復雜度是 O(1)

面試題 54：所有大于或等于節(jié)點的值之和

題目：給定一棵二叉搜索樹，請將它的每個節(jié)點的值替換成樹中大于或等于該節(jié)點值的所有節(jié)點值之和。假設二叉樹中節(jié)點的值唯一

首先需要注意到這個題目與節(jié)點值的大小順序相關，因為要找出比某節(jié)點的值大的所有節(jié)點。在二叉搜索樹的常用遍歷算法中，只有中序遍歷是按照節(jié)點值遞增的順序遍歷所有節(jié)點的……

如果能夠按照節(jié)點值從大到小的順序遍歷二叉搜索樹……通常的中序遍歷是先遍歷左子樹，再遍歷根節(jié)點，最后遍歷右子樹……那么只需要改變中序遍歷的順序，先遍歷右子樹，再遍歷根節(jié)點，最后遍歷左子樹，這樣遍歷的順序就顛倒過來了

基于這種顛倒的中序遍歷，可以編寫出如下所示的代碼：

public static TreeNode convertBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    int sum = 0;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        sum += cur.val;
        cur.val = sum;
        cur = cur.left;
    }
    return root;
}

面試題 55：二叉搜索樹迭代器

題目：請實現(xiàn)二叉搜索樹迭代器 BSTIterator，它主要有如下 3 個函數(shù)

• 構造函數(shù)：輸入二叉樹的根節(jié)點初始化該迭代器
• 函數(shù) next：返回二叉搜索樹中下一個最小的節(jié)點的值
• 函數(shù) hasNext：返回二叉搜索樹是否還有下一個節(jié)點

基于中序遍歷的迭代代碼實現(xiàn)二叉搜索樹的迭代器的參考代碼如下所示：

class BSTIterator {
    TreeNode cur;
    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new Stack<>();
    }

    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }

    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.right;
        return val;
    }
}

在上述代碼中，棧 stack 的大小為 O(h)。由于這個棧一直存在，因此函數(shù) hasNext 和 next 的空間復雜度是 O(h)。函數(shù) hasNext 的時間復雜度顯然是 O(1)。如果二叉搜索樹有 n 個節(jié)點，調用 n 次函數(shù) next 才能遍歷完所有的節(jié)點，因此函數(shù) next 的平均時間復雜度是 O(1)

面試題 56：二叉搜索樹中兩個節(jié)點的值之和

題目：給定一棵二叉搜索樹和一個值 k，請判斷該二叉搜索樹中是否存在值之和等于 k 的兩個節(jié)點。假設二叉搜索樹中節(jié)點的值均唯一

利用哈希表，空間復雜度為 O(n) 的解法

public static boolean findTarget1(TreeNode root, int k) {
    Set<Integer> set = new HashSet<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (set.contains(k - cur.val)) {
            return true;
        }
        set.add(cur.val);
        cur = cur.right;
    }
    return false;
}

上述算法其實適合任何二叉樹，并沒有利用二叉搜索樹的特性。接下來根據二叉搜索樹的特性做進一步的優(yōu)化

應用雙指針，空間復雜度為 O(h) 的解法

面試題 6 介紹了如何利用雙指針判斷在排序數(shù)組中是否包含兩個和為 k 的數(shù)字，即把第 1 個指針指向數(shù)組的第 1 個（也是最小的）數(shù)字，把第 2 個指針指向數(shù)組的最后一個（也是最大的）數(shù)字。如果兩個數(shù)字之和等于 k，那么就找到了兩個符合要求的數(shù)字；如果兩個數(shù)字之和大于 k，那么向左移動第 2 個指針使它指向更小的數(shù)字；如果兩個數(shù)字之和小于 k，那么向右移動第 1 個指針使它指向更大的數(shù)字……

class BSTIteratorReversed {
    TreeNode cur;
    Stack<TreeNode> stack;

    public BSTIteratorReversed(TreeNode root) {
        cur = root;
        stack = new Stack<>();
    }

    public boolean hasPrev() {
        return cur != null || !stack.isEmpty();
    }

    public int prev() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.left;
        return val;
    }
}

有了 BSTIteratorReversed 的迭代器，每次調用函數(shù) prev 都將按照從大到小的順序從二叉搜索樹中取出一個節(jié)點的值……可以很容易地運用雙指針的思路，其參考代碼如下所示：

public static boolean findTarget2(TreeNode root, int k) {
    if (root == null) {
        return false;
    }
    BSTIterator iterNext = new BSTIterator(root);
    BSTIteratorReversed iterPrev = new BSTIteratorReversed(root);
    int next = iterNext.next();
    int prev = iterPrev.prev();
    while (next != prev) {
        if (next + prev == k) {
            return true;
        }
        if (next + prev < k) {
            next = iterNext.next();
        } else {
            prev = iterPrev.prev();
        }
    }
    return false;
}

……如果它們的和小于 k，就用 BSTIterator 取出一個更大的節(jié)點值；如果它們的和大于 k，就用 BSTIteratorReversed 取出一個更小的節(jié)點值

這兩個迭代器一起使用可能需要遍歷整棵二叉搜索樹，因此時間復雜度是 O(n)。每個迭代器都需要一個大小為 O(h) 的棧，因此總的空間復雜度是 O(h)。在大多數(shù)情況下，二叉樹的深度遠小于二叉樹的節(jié)點數(shù)，因此第二種算法的總體空間效率要優(yōu)于第 1 種算法

TreeSet 和 TreeMap 的應用

二叉搜索樹是一種很有用的數(shù)據結構。如果二叉搜索樹有 n 個節(jié)點，深度為 h，那么查找、添加和刪除操作的時間復雜度都是 O(h)。如果二叉搜索樹是平衡的，那么深度 h 近似等于 logn。但在極端情況下（如每個節(jié)點只有一個子節(jié)點），樹的深度 h 等于 n-1，此時二叉搜索樹的查找、添加和刪除操作的時間復雜度都退化成 O(n)。二叉搜索樹是否平衡對二叉搜索樹的時間效率至關重要

實現(xiàn)一棵平衡的二叉搜索樹對于面試來說并不是一件容易的事情。Java 根據紅黑樹這種平衡的二叉搜索樹實現(xiàn) TreeSet 和 TreeMap 兩種數(shù)據結構，如果應聘者在面試的時候需要使用平衡的二叉樹來高效地解決問題，則可以直接引用

TreeSet 實現(xiàn)了接口 Set，它內部的平衡二叉樹中每個節(jié)點只包含一個值，根據這個值的查找、添加和刪除操作的時間復雜度都是 O(logn)。除 Set 定義的接口之外，TreeSet 的常用函數(shù)如下表所示：

TreeMap 實現(xiàn)了接口 Map。和 TreeSet 不一樣，TreeMap 內部的平衡二叉搜索樹中的每個節(jié)點都是一個包含鍵值和值的映射?？梢愿鶕I值實現(xiàn)時間復雜度為 O(logn) 的查找、添加和刪除操作。除 Map 定義的接口之外，TreeMap 的常用函數(shù)如下表所示：

如果面試題的數(shù)據集合是動態(tài)的（即題目要求逐步在數(shù)據集合中添加更多的數(shù)據），并且需要根據數(shù)據的大小實現(xiàn)快速查找，那么可能需要用到 TreeSet 或 TreeMap

第 5 章介紹了哈希表（HashSet 或 HashMap）中查找、添加和刪除操作的時間復雜度都是 O(1)，是非常高效的。但它有一個缺點，哈希表只能根據鍵進行查找，只能判斷該鍵是否存在。如果需要根據數(shù)值的大小查找，如查找數(shù)據集合中比某個值大的所有數(shù)字中的最小的一個，哈希表就無能為力

如果在一個排序的動態(tài)數(shù)組（如 Java 的 ArrayList）中根據數(shù)值的大小進行查找，則可以應用二分查找算法實現(xiàn)時間效率為 O(logn) 的查找。但排序的動態(tài)數(shù)組的添加和刪除操作的時間復雜度是 O(n)

由于 TreeSet 或 TreeMap 能夠保證其內部的二叉搜索樹是平衡的，因此它們的查找、添加和刪除操作的時間復雜度都是 O(logn)，綜合來看它們比動態(tài)排序數(shù)組更加高效

面試題 57：值和下表之差都在給定的范圍內

題目：給定一個整數(shù)數(shù)組 nums 和兩個正數(shù) k、t，請判斷是否存在兩個不同的下標 i 和 j 滿足 i 和 j 之差的絕對值不大于給定的 k，并且兩個數(shù)值 nums[i] 和 nums[j] 的差的絕對值不大于給定的 t

例如，如果輸入數(shù)組 {1, 2, 3, 1}，k 為 3，t 為 0，由于下標 0 和下標 3 對應的數(shù)字之差的絕對值為 0，因此返回 true。如果輸入數(shù)組 {1, 5, 9, 1, 5, 9}，k 為 2，t 為 3，由于不存在兩個下標之差小于或等于 2 且它們差的絕對值小于或等于 3 的數(shù)字，因此此時應該返回 false

首先考慮最直觀的解法?？梢灾鹨粧呙钄?shù)組中的每個數(shù)字。對于每個數(shù)字 nums[i]，需要逐一檢查它前面的 k 個數(shù)字是否存在從 nums[i]-t 到 nums[i]+t 的范圍內的數(shù)字。如果存在，則返回 true。這種思路很容易用兩個嵌套的循環(huán)實現(xiàn)

由于數(shù)組中的每個數(shù)字都要和 k 個數(shù)字進行比較，如果數(shù)組的長度為 n，那么這種解法的時間復雜度是 O(nk)

時間復雜度為 O(nlogk) 的解法

接下來嘗試優(yōu)化時間復雜度。逐一掃描數(shù)組中的每個數(shù)字。對于每個數(shù)字 nums[i]，應該先從它前面的 k 個數(shù)字中找出小于或等于 nums[i] 的最大的數(shù)字，如果這個數(shù)字與 nums[i] 的差的絕對值不大于 t，那么就找到了一組符合條件的兩個數(shù)字。否則，再從它前面的 k 個數(shù)字中找出大于或等于 nums[i] 的最小的數(shù)字，如果這個數(shù)字與 nums[i] 的差的絕對值不大于 t，就找到了一組符合條件的兩個數(shù)字

需要從一個大小為 k 的內容變化的數(shù)據容器中找出小于或等于某個數(shù)字的最大值及大于或等于某個數(shù)字的最小值，這正是 TreeSet 或 TreeMap 適用的場景。因為這個容器只需要保存數(shù)字，所以可以用 TreeSet 來保存每個數(shù)字 nums[i] 前面的 k 個數(shù)字?；?TreeSet 的參考代碼如下所示：

public static boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
    TreeSet<Long> set = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
        Long lower = set.floor((long) nums[i]);
        if (lower != null && lower >= (long) nums[i] - t) {
            return true;
        }
        Long upper = set.ceiling((long) nums[i]);
        if (upper != null && upper <= (long) nums[i] + t) {
            return true;
        }
        set.add((long) nums[i]);
        if (i >= k) {
            set.remove((long) nums[i - k]);
        }
    }
    return false;
}

在上述代碼中，變量 set 是一個 TreeSet，它的大小為 k，因此空間復雜度是 O(k)。對它做查找、添加和刪除操作的時間復雜度都是 O(logk)，因此對于一個長度為 n 的數(shù)組而言，它的時間復雜度是 O(nlogk)

時間復雜度為 O(n) 的解法

下面換一種思路來解決這個問題。由于這個題目關心的是差的絕對值小于或等于 t 的數(shù)字，因此可以將數(shù)字放入若干大小為 t+1 的桶中。例如，將從 0 到 t 的數(shù)字放入編號為 0 的桶中，從 t+1 到 2t+1 的數(shù)字放入編號為 1 的桶中。其他數(shù)字以此類推。這樣做的好處是如果兩個數(shù)字被放入同一個桶中，那么它們的差的絕對值一定小于或等于 t

還是逐一掃描數(shù)組中的數(shù)字。如果當前掃描到數(shù)字 num，那么它將放入編號為 id 的桶中。如果這個桶中之前已經有數(shù)字，那么就找到兩個差的絕對值小于或等于 t 的數(shù)字。如果桶中之前沒有數(shù)字，則再判斷編號為 id-1 和 id+1 的這兩個相鄰桶中是否存在與 num 的差的絕對值小于或等于 t 的數(shù)字。因為其他桶中的數(shù)字與 num 的差的絕對值一定大于 t，所以不需要判斷其他的桶中是否有符合條件的數(shù)字

基于這種思路編寫的代碼如下所示：

public static boolean containsNearByAlmostDuplicate2(int[] nums, int k, int t) {
    Map<Integer, Integer> buckets = new HashMap<>();
    int bucketSize = t + 1;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        int id = getBucketId(num, bucketSize);
        if (buckets.containsKey(id)
                || (buckets.containsKey(id - 1) && buckets.get(id - 1) + t >= num)
                || (buckets.containsKey(id + 1) && buckets.get(id + 1) - t <= num)) {
            return true;
        }
        buckets.put(id, num);
        if (i >= k) {
            buckets.remove(getBucketId(nums[i - k], bucketSize));
        }
    }
    return false;
}

private static int getBucketId(int num, int bucketSize) {
    return num >= 0 ? num / bucketSize : (num + 1) / bucketSize - 1;
}

在上述代碼中，隨著下標的移動，總是有最多 k 個桶來存儲數(shù)組 nums 的值，每個桶中只有一個數(shù)字（當需要往同一個桶中裝入兩個數(shù)字時，意味著數(shù)字的差的絕對值小于或等于 t，意味著方法結束，返回 true）

哈希表 buckets 的大小是 k，因此，空間復雜度是 O(k)。哈希表中的查找、添加和刪除操作的時間復雜度都是 O(1)，因此，對于一個長度為 n 的數(shù)組而言，它的時間復雜度是 O(n)

面試題 58：日程表

題目：請實現(xiàn)一個類型 MyCalendar 用來記錄自己的日程安排，該類型用方法 book(int start, int end) 在日程表中添加一個時間區(qū)域為 [start, end) 的事項（這是一個半開半閉區(qū)間）。如果 [start, end) 中之前沒有安排其他事項，則成功添加該事項并返回 true；否則，不能添加該事項，并返回 false

如果待添加的事項占用的時間區(qū)間是 [m, n)，就需要找出開始時間小于 m 的所有事項中開始最晚的一個，以及開始時間大于 m 的所有事項中開始最早的一個。如果待添加的事項和這兩個事項都沒有重疊，那么該事項可以添加在日程表中（之前的事項都是這樣添加的，因此各不重疊）

基于 TreeMap 的參考代碼如下所示：

class MyCalendar {
    private TreeMap<Integer, Integer> events;

    public MyCalendar() {
        events = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> event = events.floorEntry(start);
        if (event != null && event.getValue() > start) {
            return false;
        }
        event = events.ceilingEntry(start);
        if (event != null && event.getKey() < end) {
            return false;
        }
        events.put(start, end);
        return true;
    }
}

本章小結

本章介紹了樹這種數(shù)據結構，尤其著重介紹了二叉樹。與二叉樹相關的面試題大多與遍歷相關，本章通過大量的面試題全面介紹了二叉樹的中序遍歷、前序遍歷和后序遍歷這 3 種深度優(yōu)先搜索算法。筆者強烈建議讀者對這 3 種遍歷的循環(huán)和迭代代碼爛熟于心，這樣在解決與二叉樹相關的面試題時才能得心應手

二叉搜索樹是一種特殊的二叉樹，在二叉搜索樹中進行搜索、添加和刪除操作的平均時間復雜度都是 O(logn)。如果按照中序遍歷的順序遍歷一棵二叉搜索樹，那么按照從小到大的順序依次遍歷每個節(jié)點。由于這個特性，與二叉搜索樹相關的很多面試題都適合使用中序遍歷解決

Java 中提供的 TreeSet 和 TreeMap 這兩種數(shù)據結構實現(xiàn)了平衡二叉搜索樹。如果需要動態(tài)地在一個排序的數(shù)據集合中添加元素，或者需要根據數(shù)據的大小查找，那么可以使用 TreeSet 或 TreeMap 解決文章來源地址http://www.zghlxwxcb.cn/news/detail-715684.html

到了這里，關于Java 數(shù)據結構與算法-樹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！