LeetCode 總結(jié) - 搞定 Binary Tree 面試題

題量有點多，建議Ctrl + F題號或題目哦~

二叉樹的遍歷（前序遍歷，中序遍歷，后序遍歷）

[144] Binary Tree Preorder Traversal 二叉樹前序遍歷

https://leetcode.com/problems/binary-tree-preorder-traversal

問題：二叉樹前序遍歷。

思路：用一個棧來實現(xiàn)，由于遍歷過程中要先訪問樹的左子樹，而后右子樹，所以實現(xiàn)的時候先把根節(jié)點的右孩子入棧，而后是左孩子。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        results.add(node.val);
        // 先壓右后壓左，這樣pop遍歷時的順序就是先左后右
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return results;
}

參考講解：

[94] Binary Tree Inorder Traversal 二叉樹中序遍歷

https://leetcode.com/problems/binary-tree-inorder-traversal

問題：二叉樹中序遍歷。

思路：由于二叉樹中序遍歷要先遍歷左孩子，再是根節(jié)點，最后是右孩子。所以算法先找到根節(jié)點的最左孩子，把一路下來的左孩子依次入棧，訪問最左孩子，而后是訪問根節(jié)點，然后把根節(jié)點右孩子當(dāng)做當(dāng)前節(jié)點。重復(fù)上述過程直到節(jié)點都訪問完。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.empty()) {
        // 左孩子依次入棧，訪問最左孩子
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        // cur為空循環(huán)結(jié)束，說明已經(jīng)到達(dá)最左下節(jié)點，訪問它并添加到結(jié)果
        node = stack.pop();
        results.add(node.val);
        // 把根節(jié)點右孩子當(dāng)做當(dāng)前節(jié)點
        node = node.right;
    }
    return results;
}

參考講解：

[145] Binary Tree Postorder Traversal 二叉樹后序遍歷

https://leetcode.com/problems/binary-tree-postorder-traversal

問題：二叉樹后序遍歷。

思路：

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> results = new LinkedList<>();
    if (root == null) return results;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        results.addFirst(node.val);
        if (node.left!=null) stack.push(node.left);
        if (node.right!=null) stack.push(node.right);
    }
    return results;
}

參考講解：

二叉樹的層序遍歷

[102] Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal

問題：

思路：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        // 必須要這行?。?！
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        results.add(level);
    }
    return results;
}

參考講解：

[107] Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii

問題：

思路：只要在普通的層序遍歷代碼中修改一處：results.add(0, level);，這樣每次頭插到結(jié)果中。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        // 自底向上層序遍歷，所以每次頭插到結(jié)果中
        results.add(0, level);
    }
    return results;
}

參考講解：

[103] Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal

問題：

思路：

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) return results;
    int depth = 1;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 按之字形存儲
            if (depth % 2 == 1) level.add(node.val);
            else level.add(0, node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        results.add(level);
        depth++;
    }
    return results;
}

參考講解：

二叉樹的查找

[199] Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view

問題：返回二叉樹每層的最右邊節(jié)點的值。

思路：

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 每次把每層的最右邊一個節(jié)點的值添加到results中
            if (i == size - 1) results.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return results;
}

參考講解：

[513] Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value

問題：找到二叉樹的最后一層的最左邊的值。

思路：

public int findBottomLeftValue(TreeNode root) {
    int result = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 更新每一層的最左邊元素
            if (i == 0) result = node.val;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}

參考講解：

[515] Find Largest Value in Each Tree Row

https://leetcode.com/problems/find-largest-value-in-each-tree-row

問題：

思路：

public List<Integer> largestValues(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    if (root == null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            System.out.println(queue.toArray(new TreeNode[queue.size()]).length);
        }
        results.add(Collections.max(level));
        level.clear();
    }
    return results;
}

參考講解：

[637] Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree

問題：

思路：

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> results = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        long sum = 0;
        int count = 0;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            count++;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        results.add((double) sum / count);
    }
    return results;
}

參考講解：

[671] Second Minimum Node In a Binary Tree

https://leetcode.com/problems/second-minimum-node-in-a-binary-tree

問題：每個節(jié)點要么有2個子節(jié)點，要么沒有子節(jié)點，如果有兩個子節(jié)點，這個節(jié)點的值比兩個子節(jié)點都小。

思路：可以利用特性（根節(jié)點小于等于子節(jié)點的值）來加速搜索。層序遍歷不停更新second。

public int findSecondMinimumValue(TreeNode root) {
    if (root == null) return -1;
    int first = root.val;
    int second = Integer.MAX_VALUE;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.val != first && node.val < second) second = node.val;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return (second == first || second == Integer.MAX_VALUE) ? -1 : second;
}

參考講解：

[623] Add One Row to Tree

https://leetcode.com/problems/add-one-row-to-tree

問題：

思路：

public TreeNode addOneRow(TreeNode root, int v, int d) {
    if (root == null) return null;
    // 當(dāng)d==1時，需要替換根結(jié)點
    if (d == 1) {
        TreeNode newRoot = new TreeNode(v);
        newRoot.left = root;
        return newRoot;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 檢測到 d 為 0 時，直接返回，因為添加操作已經(jīng)完成，沒必要遍歷完剩下的結(jié)點
        if (--d == 0) return root;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 當(dāng) d==1 時，需要插入該行
            if (d == 1) {
                TreeNode left = new TreeNode(v);
                left.left = node.left;
                node.left = left;
                TreeNode right = new TreeNode(v);
                right.right = node.right;
                node.right = right;
            } else {
                // 如果 d 不為 1，那么就是層序遍歷原有的入隊操作
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
    }
    return root;
}

參考講解：

[116] Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node

問題：

思路：

// 遞歸
public void connect(TreeLinkNode root) {
    if (root == null) return;
    if (root.left != null) {
        // 1的left是2，1的right是3，所以2要指向3
        root.left.next = root.right;
    }
    if (root.next != null && root.right != null) {
        // 2的right是5，2的next的left是3，所以5要指向6
        root.right.next = root.next.left;
    }
    connect(root.left);
    connect(root.right);
}

// 迭代
public void connect2(TreeLinkNode root) {
    TreeLinkNode start = root;
    // start類似于層序遍歷中的每層的最左節(jié)點
    while (start != null) {
        TreeLinkNode cur = start;
        // cur類似于層序遍歷中的一層中的各個節(jié)點
        while (cur != null) {
            if (cur.left != null) {
                cur.left.next = cur.right;
            }
            if (cur.right != null && cur.next != null) {
                cur.right.next = cur.next.left;
            }
            cur = cur.next;
        }
        start = start.left;
    }
}

參考講解：

[117] Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii

問題：

思路：

public void connect(TreeLinkNode root) {
    // head類似于層序遍歷中每層的最左節(jié)點
    TreeLinkNode head = null;
    // prev是當(dāng)前節(jié)點的前驅(qū)節(jié)點
    TreeLinkNode prev = null;
    // cur類似于層序遍歷中的一層中的各個節(jié)點
    TreeLinkNode cur = root;
    while (cur != null) {
        while (cur != null) {
            if (cur.left != null) {
                if (prev != null) {
                    prev.next = cur.left;
                } else {
                    head = cur.left;
                }
                prev = cur.left;
            }
            if (cur.right != null) {
                if (prev != null) {
                    prev.next = cur.right;
                } else {
                    head = cur.right;
                }
                prev = cur.right;
            }
            cur = cur.next;
        }
        cur = head;
        prev = null;
        head = null;
    }
}

參考講解：

[236] Lowest Common Ancestor of a Binary Tree 二叉樹的最小公共祖先

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree

問題：

思路：對于二叉搜索樹，公共祖先的值一定大于等于較小的節(jié)點，小于等于較大的節(jié)點。換言之，在遍歷樹的時候，如果當(dāng)前結(jié)點大于兩個節(jié)點，則結(jié)果在當(dāng)前結(jié)點的左子樹里，如果當(dāng)前結(jié)點小于兩個節(jié)點，則結(jié)果在當(dāng)前節(jié)點的右子樹里。
而這里不是二叉搜索樹，只能用深度優(yōu)先搜索，從葉子節(jié)點向上，標(biāo)記子樹中出現(xiàn)目標(biāo)節(jié)點的情況。如果子樹中有目標(biāo)節(jié)點，標(biāo)記為那個目標(biāo)節(jié)點，如果沒有，標(biāo)記為null。顯然，如果左子樹、右子樹都有標(biāo)記，說明就已經(jīng)找到最小公共祖先了。如果在根節(jié)點為p的左右子樹中找p、q的公共祖先，則必定是p本身。
換個角度，可以這么想：如果一個節(jié)點左子樹有兩個目標(biāo)節(jié)點中的一個，右子樹沒有，那這個節(jié)點肯定不是最小公共祖先。如果一個節(jié)點右子樹有兩個目標(biāo)節(jié)點中的一個，左子樹沒有，那這個節(jié)點肯定也不是最小公共祖先。只有一個節(jié)點正好左子樹有，右子樹也有的時候，才是最小公共祖先。
具體做法是，遞歸尋找兩個帶查詢LCA的節(jié)點p和q，當(dāng)找到后，返回給它們的父親。如果某個節(jié)點的左右子樹分別包括這兩個節(jié)點，那么這個節(jié)點必然是所求的解，返回該節(jié)點。否則，返回左或者右子樹（哪個包含p或者q的就返回哪個）。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 葉子節(jié)點左右孩子都為空，這時候返回null
    if (root == null) return null;
    // 發(fā)現(xiàn)目標(biāo)節(jié)點則通過返回值標(biāo)記該子樹發(fā)現(xiàn)了某個目標(biāo)結(jié)點
    if (root == p || root == q) return root;
    // Divide
    // 查看左子樹中是否有目標(biāo)結(jié)點，沒有為null
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 查看右子樹是否有目標(biāo)節(jié)點，沒有為null
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // Conquer
    // 左右節(jié)點都不為空，說明左右子樹都有目標(biāo)結(jié)點，則公共祖先就是本身
    if (left != null && right != null) return root;
    // 如果發(fā)現(xiàn)了目標(biāo)節(jié)點，則繼續(xù)向上標(biāo)記為該目標(biāo)節(jié)點
    return left == null ? right : left;
}

還有一種簡單的方法是DFS分別尋找到兩個節(jié)點p和q的路徑，然后對比路徑，查看他們的第一個分岔口，則為LCA。

參考講解：

[404] Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves

問題：左子葉節(jié)點之和。

思路：

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null || root.left == null && root.right == null) return 0;
    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // 左節(jié)點不為空且左節(jié)點是葉子結(jié)點，則把左節(jié)點的值添加到和里
        if (node.left != null && node.left.left == null && node.left.right == null) sum += node.left.val;
        // 左右子節(jié)點入棧
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return sum;
}

參考講解：

[654] Maximum Binary Tree

https://leetcode.com/problems/maximum-binary-tree

問題：創(chuàng)建一個最大二叉樹，創(chuàng)建規(guī)則是數(shù)組中的最大值為根結(jié)點，然后分隔出的左右部分再分別創(chuàng)建最大二叉樹。

思路：

public TreeNode constructMaximumBinaryTree(int[] nums) {
    if (nums == null || nums.length == 0) return null;
    return helper(nums, 0, nums.length);
}

public TreeNode helper(int[] nums, int left, int right) {
    if (left == right) return null;
    int maxIndex = findMax(nums, left, right);
    TreeNode root = new TreeNode(nums[maxIndex]);
    root.left = helper(nums, left, maxIndex);
    root.right = helper(nums, maxIndex + 1, right);
    return root;
}

private int findMax(int[] nums, int left, int right) {
    int maxIndex = left;
    for (int i = left; i < right; i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }
    return maxIndex;
}

參考講解：

[563] Binary Tree Tilt

https://leetcode.com/problems/binary-tree-tilt

問題：二叉樹的坡度定義為該結(jié)點的左子樹之和與右子樹之和的差的絕對值，求所有結(jié)點的坡度之和。

思路：后序遍歷，這樣就可以從葉子結(jié)點開始搜索，便于求和。

private int res = 0;

public int findTilt(TreeNode root) {
    if (root == null) return 0;
    helper(root);
    return res;
}

private int helper(TreeNode root) {
    if (root == null) return 0;
    int left = helper(root.left);
    int right = helper(root.right);
    // 左右子樹的差的絕對值
    res += Math.abs(left - right);
    // 函數(shù)的返回值是當(dāng)前根節(jié)點的值加上左右子樹的和
    return left + right + root.val;
}

參考講解：

[508] Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum

問題：

思路：后序遍歷，因為我們必須首先知道左子樹和右子樹。

private int max = Integer.MIN_VALUE;

public int[] findFrequentTreeSum(TreeNode root) {
    Map<Integer, Integer> sumToCount = new HashMap<>();
    if (root != null) countSum(root, sumToCount);
    List<Integer> maxSum = new ArrayList<>();
    for (Map.Entry<Integer, Integer> pair : sumToCount.entrySet()) {
        int count = pair.getValue();
        if (count == max) maxSum.add(pair.getKey());
    }
    int[] res = new int[maxSum.size()];
    for (int i = 0; i < maxSum.size(); i++) {
        res[i] = maxSum.get(i);
    }
    return res;
}

private int countSum(TreeNode root, Map<Integer, Integer> sumToCount) {
    int sum = root.val;
    if (root.left != null) sum += countSum(root.left, sumToCount);
    if (root.right != null) sum += countSum(root.right, sumToCount);
    int count = sumToCount.containsKey(sum) ? sumToCount.get(sum) + 1 : 1;
    sumToCount.put(sum, count);
    max = Math.max(max, count);
    return sum;
}

參考講解：

二叉樹的路徑求和

[112] Path Sum

https://leetcode.com/problems/path-sum

問題：給定一棵二叉樹和一個sum值，判斷二叉樹中是否存在一條從根節(jié)點到葉子節(jié)點的路徑，使得路徑上的值加起來剛好等于sum。

思路：樹的題目基本都是用遞歸來解決，主要考慮兩個問題：

  1. 如何把問題分治成子問題給左子樹和右子樹。這里就是看看左子樹和右子樹有沒有存在和是sum減去當(dāng)前結(jié)點值得路徑，只要有一個存在，那么當(dāng)前結(jié)點就存在路徑。
  2. 考慮結(jié)束條件是什么。這里的結(jié)束條件一個是如果當(dāng)前節(jié)點是空的，則返回false。另一個如果是葉子，那么如果剩余的sum等于當(dāng)前葉子的值，則找到滿足條件的路徑，返回true。

想清楚上面兩個問題，那么實現(xiàn)起來就是一次樹的遍歷，按照剛才的分析用參數(shù)或者返回值傳遞需要維護(hù)的值，然后按照遞歸條件和結(jié)束條件進(jìn)行返回即可。算法的時間復(fù)雜度是一次遍歷O(n)，空間復(fù)雜度是棧的大小O(logn)。

遞歸結(jié)束條件：
root == null。返回false，表示不存在；
root.left == null && root.right == null && sum - root.val == 0。返回true，表示找到了路徑。

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    return helper(root, 0, sum);
}

private boolean helper(TreeNode root, int sum, int target) {
    boolean left = false;
    boolean right = false;
    sum += root.val;
    if (sum == target && root.left == null && root.right == null) return true;
    if (root.left != null) left = helper(root.left, sum, target);
    if (root.right != null) right = helper(root.right, sum, target);
    return left || right;
}

參考講解：

[113] Path Sum II

https://leetcode.com/problems/path-sum-ii

問題：找到所有從根節(jié)點到葉子結(jié)點的路徑和為sum的路徑。

思路：回溯法。其實思路和Path Sum是完全一樣的，只是需要輸出所有路徑，所以需要數(shù)據(jù)結(jié)構(gòu)來維護(hù)路徑，添加兩個參數(shù)，一個用來維護(hù)走到當(dāng)前結(jié)點的路徑，一個用來保存滿足條件的所有路徑，思路上遞歸條件和結(jié)束條件是完全一致的，空間上這里會依賴于結(jié)果的數(shù)量了。
具體做法是，將當(dāng)前節(jié)點root的值放入list中更新sum值，判斷當(dāng)前節(jié)點是否滿足遞歸條件root.left == null && root.right == null&&sum == 0。若滿足，則將存有當(dāng)前路徑的list值存入最后的大list中，然后依次遞歸左子樹和右子樹，從存有當(dāng)前路徑的list中去除最后一個節(jié)點，這樣便可以返回到了當(dāng)前葉子節(jié)點的父節(jié)點。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) return results;
    helper(root, 0, sum, new ArrayList<>(), results);
    return results;
}

private void helper(TreeNode root, int sum, int target, List<Integer> path, List<List<Integer>> results) {
    if (root == null) return;
    sum += root.val;
    path.add(root.val);
    if (root.left == null && root.right == null) {
        if (sum == target) {
            results.add(new ArrayList<>(path));
        }
    }
    helper(root.left, sum, target, path, results);
    helper(root.right, sum, target, path, results);
    path.remove(path.size() - 1);
}

參考講解：

[437] Path Sum III

https://leetcode.com/problems/path-sum-iii

問題：路徑的定義不必從根節(jié)點開始，也不必終止與葉子節(jié)點，只需要保證從父節(jié)點指向子節(jié)點即可。

思路：我們定義一個輔助函數(shù) path（TreeNode root，int sum），表示在以node為根節(jié)點的二叉樹中，尋找包含node的路徑，和為sum，返回路徑的個數(shù)。該函數(shù)的返回值由三部分組成：

  1. 當(dāng)前root.val是否等于sum
  2. 左子樹遞歸
  3. 右子樹遞歸

由于路徑的根節(jié)點可以不是從該樹的root節(jié)點開始，所以還需要遞歸計算root.left和root.right作為根節(jié)點的路徑個數(shù)。

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    // 把左右節(jié)點重新看做一個根節(jié)點
    return helper(root, 0, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int helper(TreeNode root, int sum, int target) {
    if (root == null) return 0;
    int res = 0;
    sum += root.val;
    // 這里不能直接退出，而是res++，然后遍歷左右子樹，最后再返回
    if (sum == target) res++;
    res += helper(root.left, sum, target) + helper(root.right, sum, target);
    return res;
}

參考講解：

[257] Binary Tree Paths

https://leetcode.com/problems/binary-tree-paths

問題：

思路：不需要計算路徑和，只需要無腦返回所有的路徑即可，直接用DFS（遞歸或分治）。

public List<String> binaryTreePaths(TreeNode root) {
    List<String> results = new ArrayList<>();
    if (root == null) return results;
    helper(root, new StringBuilder(), results);
    return results;
}

private void helper(TreeNode root, StringBuilder path, List<String> results) {
    // 遞歸結(jié)束條件1
    if (root == null) return;
    // 保存未進(jìn)行進(jìn)一步操作的字符串長度，以便后面的回溯
    int len = path.length();
    path.append(root.val).append("->");
    if (root.left == null && root.right == null) {
        // 遞歸結(jié)束條件2，到達(dá)葉子結(jié)點，收集路徑（注意把"->"截取掉）
        results.add(path.toString().substring(0, path.length() - 2));
    } else {
        if (root.left != null) helper(root.left, path, results);
        if (root.right != null) helper(root.right, path, results);
    }
    // 在遞歸調(diào)用中任何對局部變量的修改都需要回溯，以保證最上層調(diào)用者使用的局部變量和傳入時的值一樣
    path.setLength(len);
}

更簡潔的一個答案：

public List<String> binaryTreePaths(TreeNode root) {
    List<String> results = new ArrayList<>();
    if (root == null) return results;
    helper(root, root.val + "", results);
    return results;
}

private void helper(TreeNode root, String path, List<String> results) {
    if (root.left == null && root.right == null) results.add(path);
    if (root.left != null) helper(root.left, path + "->" + root.left.val, results);
    if (root.right != null) helper(root.right, path + "->" + root.right.val, results);
}

參考講解：

[129] Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers

問題：給定一個值范圍在[0,9]的二叉樹，每個root-leaf的路徑都代表一個數(shù)字，求這些數(shù)字的和。

思路：只需在遍歷過程中記錄路徑中的數(shù)字，在到達(dá)葉節(jié)點的時候把記錄下來的數(shù)字轉(zhuǎn)換成數(shù)值，加到和里面即可。遞歸條件是把當(dāng)前的sum*10 加上子節(jié)點的值進(jìn)行下一輪遞歸，結(jié)束條件是到子節(jié)點是空的時候就返回0。
算法的本質(zhì)是一次先序遍歷，所以時間是O(n)，空間是棧大小，O(logn)。

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

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

參考講解：

[543] Diameter of Binary Tree 二叉樹的直徑

https://leetcode.com/problems/diameter-of-binary-tree

問題：給定一個二叉樹，你需要去計算它的直徑。二叉樹的直徑就是任意兩個節(jié)點間最長的路徑長度。這條路徑可以通過也可以不通過根節(jié)點。注意：兩個節(jié)點間的路徑長度是計算的兩個節(jié)點間連線的個數(shù)（也就是邊的個數(shù)）。

思路：采用后序遍歷即可。這道題首先很容易想到從根節(jié)點開始，分別計算左右子節(jié)點的深度然后相加即為結(jié)果，這種思路是最容易誤入的。因為最長路徑很可能是不經(jīng)過根節(jié)點的。那么從深度優(yōu)先搜索DFS的思想出發(fā)，從某一節(jié)點開始，計算以該節(jié)點為根節(jié)點的最長路徑，并將其與之前的最長路徑進(jìn)行比較，若大于當(dāng)前最長路徑，則新路徑為最長路徑，否則之前的路徑仍舊為最長路徑。在計算某一節(jié)點的最長路徑時，即為該節(jié)點開始左右子樹的深度和。那么DFS遍歷這棵二叉樹的每一個節(jié)點，就可以計算出這棵二叉樹兩葉子節(jié)點之間的最長路徑了。

面對樹結(jié)構(gòu)，常理采用recursion。判斷左邊+右邊是否最長，回溯則選擇最長的一邊。這個問題可以分兩個方面來考慮：

  1. 最長路徑經(jīng)過根節(jié)點：那么根節(jié)點的左子樹的深度和右子樹的深度就是我們的結(jié)果
  2. 最長路徑?jīng)]有經(jīng)過根節(jié)點：這個問題就分為兩個子問題，分別設(shè)置新的根節(jié)點為其左子節(jié)點和右子節(jié)點，然后重復(fù)步驟 1
private int diameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    // 空節(jié)點或者左右孩子均為空的節(jié)點
    if (root == null || (root.left == null && root.right == null)) return 0;
    helper(root);
    return diameter;
}

// 此函數(shù)返回樹的最大深度
private int helper(TreeNode root) {
    if (root == null) return 0;
    int left = helper(root.left);
    int right = helper(root.right);
    // 左子樹和右子樹的深度相加就是根該節(jié)點的直徑
    diameter = Math.max(diameter, left + right);
    // 返回節(jié)點左右子樹中較大的深度
    return Math.max(left, right) + 1;
}

參考講解：

[687] Longest Univalue Path

https://leetcode.com/problems/longest-univalue-path

問題：二叉樹的最長路徑（按邊數(shù)算），路徑上的每個節(jié)點的值都相同，可以不經(jīng)過root。

思路：這題直覺就是要用 Recursive 的方式。概念在於:
(1) 如果 node 和它的 child tree root node 的值相等，那 child tree 的最長路徑+1 就是該 node 那一邊 child tree 的最長路徑。
如果 node 和它的 child tree root node 的值不相等，那一邊 child tree 的最長路徑對這個 node 來說就無意義，等於 0。
(2) 這部分會有個容易出錯的地方，就是算某一個 node 的給 parent node 用的最長路徑和算該 node 的最長路徑會有差別。
算該 node 的最長路徑 = 左 child tree + 右 child tree (值都相同的情況下)
算該 node 的 parent node 最長路徑 = max(左 child tree , 右 child tree) (值都相同的情況下)
如果值不同，那那邊 child tree 路徑 = 0。

private int maxLen;

public int longestUnivaluePath(TreeNode root) {
    if (root == null) return 0;
    helper(root);
    return maxLen;
}

private int helper(TreeNode root) {
    if (root == null) return 0;
    // 求出左右子樹的單邊最長UnivaluePath
    int left = helper(root.left);
    int right = helper(root.right);
    left = (root.left != null && root.val == root.left.val) ? left + 1 : 0;
    right = (root.right != null && root.val == root.right.val) ? right + 1 : 0;
    // 可以更新雙邊的情況
    maxLen = Math.max(maxLen, left + right);
    // 只能返回長度較大的一邊
    return Math.max(left, right);
}

參考講解：

[124] Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum

問題：二叉樹的最大路徑和（可以是任意兩個節(jié)點）。

思路：后序遍歷，因為要從葉子結(jié)點開始遍歷。

private int result = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    if (root == null) return 0;
    helper(root);
    return result;
}

private int helper(TreeNode root) {
    if (root == null) return 0;
    // 小于0就沒有必要加入
    int left = Math.max(0, helper(root.left));
    int right = Math.max(0, helper(root.right));
    int sum = left + right + root.val;
    // result和返回的結(jié)果在本次循環(huán)中完全沒有聯(lián)系
    result = Math.max(result, sum);
    // 返回時只能返回路徑和較大一邊
    // root.val就算是負(fù)值也必須被使用
    return Math.max(left, right) + root.val;
}

參考講解：

構(gòu)建二叉樹

[105] Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

問題：根據(jù)前序遍歷和中序遍歷的結(jié)果建立二叉樹。

思路：先序遍歷可以直到根節(jié)點，而中序遍歷可以確定該根節(jié)點的左右子樹的取值范圍，從而不斷拆分下去，最終求解。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length != inorder.length) return null;
    return helper(0, 0, inorder.length - 1, preorder, inorder);
}

private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
    if (preStart > preorder.length - 1 || inStart > inEnd) return null;
    // preorder的第一個元素一定是二叉樹的根節(jié)點
    TreeNode root = new TreeNode(preorder[preStart]);
    // 表示在inorder中當(dāng)前根節(jié)點的位置
    int inRoot = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root.val) {
            inRoot = i;
            break;
        }
    }
    // preorder中當(dāng)前根節(jié)點右邊一個元素一定是根節(jié)點的左孩子
    // 左孩子一定在preorder的后部分[preStart+1,end]中，inorder的前部分[inStart,inIndex-1]中
    root.left = helper(preStart + 1, inStart, inRoot - 1, preorder, inorder);
    // inorder中當(dāng)前根節(jié)點右邊一個元素一定是根節(jié)點的右孩子
    // 通過inorder找到左孩子一共有多少個(inIndex-inStart)，這樣就可以得到右子樹的起始位置
    root.right = helper(preStart + (inRoot - inStart) + 1, inRoot + 1, inEnd, preorder, inorder);
    return root;
}

參考講解：

[106] Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

問題：根據(jù)中序遍歷和后序遍歷的結(jié)果建立二叉樹。

思路：

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || postorder == null || inorder.length != postorder.length) return null;
    // 保存中序遍歷根節(jié)點索引
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
    return helper(0, inorder.length - 1, 0, postorder.length - 1, inorder, postorder, map);
}

private TreeNode helper(int inStart, int inEnd, int postStart, int postEnd, int[] inorder, int[] postorder, Map<Integer, Integer> map) {
    if (postStart > postEnd || inStart > inEnd) return null;
    // postorder的最后一個元素一定是二叉樹的根節(jié)點
    TreeNode root = new TreeNode(postorder[postEnd]);
    int inRoot = map.get(postorder[postEnd]);
    root.left = helper(inStart, inRoot - 1, postStart, postStart + (inRoot - inStart - 1), inorder, postorder, map);
    root.right = helper(inRoot + 1, inEnd, postStart + (inRoot - inStart), postEnd - 1, inorder, postorder, map);
    return root;
}

參考講解：

[606] Construct String from Binary Tree

https://leetcode.com/problems/construct-string-from-binary-tree

問題：

思路：

public String tree2str(TreeNode t) {
    if (t == null) return "";
    StringBuilder sb = new StringBuilder();
    helper(t, sb);
    // 去掉首尾的括號
    return sb.subSequence(1, sb.length() - 1).toString();
}

private void helper(TreeNode t, StringBuilder sb) {
    // 如果當(dāng)前結(jié)點不存在，直接返回
    if (t == null) return;
    // 在當(dāng)前結(jié)點值前面加上左括號
    sb.append("(" + t.val);
    // 如果左子結(jié)點不存在而右子結(jié)點存在，要在結(jié)果 sb 后加上個空括號
    if (t.left == null && t.right != null) sb.append("()");
    // 分別對左右子結(jié)點調(diào)用遞歸函數(shù)
    helper(t.left, sb);
    helper(t.right, sb);
    // 調(diào)用完之后要加上右括號，形成封閉的括號
    sb.append(")");
}

參考講解：

二叉樹的性質(zhì)

[104] Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree

問題：

思路1（DFS）：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

思路2（迭代）：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;    
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        depth++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

參考講解：

[111] Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree

問題：

思路：當(dāng)求最大深度時，我們只要在左右子樹中取較大的就行了，然而最小深度時，如果左右子樹中有一個為空會返回0，這時我們是不能算做有效深度的。
所以分成了三種情況，左子樹為空，右子樹為空，左右子樹都不為空。當(dāng)然，如果左右子樹都為空的話，就會返回1。

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int depth = 0;
    if (root.left != null && root.right == null) {
        depth = minDepth(root.left);
    } else if (root.left == null && root.right != null) {
        depth = minDepth(root.right);
    } else {
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return Math.min(left, right);
    }
    return depth + 1;
}

迭代：

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        depth++;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

參考講解：

[662] Maximum Width of Binary Tree

https://leetcode.com/problems/maximum-width-of-binary-tree

問題：

思路：根據(jù)題目中的描述可知，這里的最大寬度不是滿樹的時候的最大寬度，如果是那樣的話，肯定是最后一層的結(jié)點數(shù)最多。這里的最大寬度應(yīng)該是兩個存在的結(jié)點中間可容納的總的結(jié)點個數(shù)，中間的結(jié)點可以為空。我們可以根據(jù)左子樹節(jié)點是根節(jié)點的2倍來做。

public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int result = 0;
    // 用于樹的廣度優(yōu)先遍歷
    Queue<TreeNode> queue = new LinkedList<>();
    // 用于保存上面隊列中樹節(jié)點對應(yīng)的位置標(biāo)號
    Queue<Integer> queuePos = new LinkedList<>();
    queue.offer(root);
    // 在頂層跟結(jié)點位置為1
    queuePos.add(1);
    // 首先判斷此隊列是否為空
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 每一層中第一個節(jié)點的下標(biāo)
        int start = queuePos.peek();
        // 每一層中最大孩子的位置下標(biāo)
        int end = start;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            end = queuePos.poll();
            // 從左子樹頭節(jié)點開始，走到最后一個節(jié)點
            if (node.left != null) {
                queue.offer(node.left);
                // 左孩子的下標(biāo)
                queuePos.offer(2 * end);
            }
            // 從右子樹頭節(jié)點開始，走到最后一個節(jié)點
            if (node.right != null) {
                queue.offer(node.right);
                // 右孩子的下標(biāo)
                queuePos.offer(2 * end + 1);
            }
        }
        result = Math.max(end - start + 1, result);
    }
    return result;
}

參考講解：

[100] Same Tree

https://leetcode.com/problems/same-tree

問題：判斷兩棵二叉樹是否完全相同。

思路：

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if ((p == null && q != null) || (p != null && q == null)) return false;
    if (p.val != q.val) return false;
    // 左右子樹都完全相同，兩棵樹才完全相等
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    // 上面的不能Accept，下面一行可以解決所有test case
    //return s != null && (isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t));
}

參考講解：

[101] Symmetric Tree

https://leetcode.com/problems/symmetric-tree

問題：

思路：

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return helper(root.left, root.right);
}

private boolean helper(TreeNode left, TreeNode right) {
    if (left == null || right == null) return left == right;
    if (left.val != right.val) return false;
    return (helper(left.left, right.right) && helper(left.right, right.left));
}

參考講解：

[572] Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree

問題：判斷t是否和s的某個子樹完全相同。

思路1（DFS）：先從s的根結(jié)點開始，跟t比較，如果兩棵樹完全相同，那么返回true。否則就分別對s的左子結(jié)點和右子結(jié)點調(diào)用遞歸再次來判斷是否相同，只要有一個返回true了，就表示可以找得到。

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    // 先從s的根結(jié)點開始，跟t比較，如果兩棵樹完全相同，那么返回true
    if (isSameTree(s, t)) return true;
    // 否則就分別對 s 的左子結(jié)點和右子結(jié)點調(diào)用遞歸再次來判斷是否相同，只要有一個返回 true 了，就表示可以找得到
    return isSameTree(s.left, t) || isSameTree(s.right, t);
}

private boolean isSameTree(TreeNode s, TreeNode t) {
    if (s == null && t == null) return true;
    if (s == null || t == null) return false;
    if (s.val != t.val) return false;
    // 左右子樹都完全相同，兩棵樹才完全相等
    return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}

思路2（迭代遍歷）：

public boolean isSubtreeIterative(TreeNode s, TreeNode t) {
    Queue<TreeNode> nodes = new ArrayDeque<>();
    nodes.offer(s);
    while (!nodes.isEmpty()) {
        TreeNode node = nodes.poll();
        if (isSameTree(node, t)) return true;
        if (node.left != null) nodes.offer(node.left);
        if (node.right != null) nodes.offer(node.right);
    }
    return false;
}

參考講解：

[226] Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree

問題：

思路：遞歸地把左子樹和右子樹取出來，再進(jìn)行調(diào)換。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
    // 將當(dāng)前節(jié)點的左右分支進(jìn)行對調(diào)反轉(zhuǎn)
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    // 若左分支存在，則遞歸左分支的節(jié)點
    if (root.left != null) invertTree(root.left);
    // 若右分支存在，則遞歸右分支的節(jié)點
    if (root.right != null) invertTree(root.right);
    // 所有的節(jié)點遍歷完成后，返回根節(jié)點
    return root;
}

參考講解：

二叉樹的序列化

[652] Find Duplicate Subtrees

https://leetcode.com/problems/find-duplicate-subtrees

問題：

思路：

參考講解：

[297] Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree

問題：

思路：

private static final String spliter = ",";
private static final String NN = "X";

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    buildString(root, sb);
    return sb.toString();
}

private void buildString(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append(NN).append(spliter);
    } else {
        sb.append(node.val).append(spliter);
        buildString(node.left, sb);
        buildString(node.right, sb);
    }
}

public TreeNode deserialize(String data) {
    Deque<String> nodes = new LinkedList<>();
    nodes.addAll(Arrays.asList(data.split(spliter)));
    return buildTree(nodes);
}

private TreeNode buildTree(Deque<String> nodes) {
    String val = nodes.remove();
    if (val.equals(NN)) return null;
    else {
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

參考講解：

平衡二叉樹

[110] Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree

問題：判斷二叉樹是否為平衡二叉樹（左右子樹的高度不大于1）。

思路：以當(dāng)前節(jié)點為根節(jié)點判斷高度差，再以左右子節(jié)點為根節(jié)點進(jìn)行判斷。

O(nlogn)解法：

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int left = depth(root.left);
    int right = depth(root.right);
    return Math.abs(left - right) > 1 && isBalanced(root.left) && isBalanced(root.right);
}

public int depth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(depth(root.left), depth(root.right)) + 1;
}

O(n)解法：

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    return depth(root) != -1;
}

public int depth(TreeNode root) {
    if (root == null) return 0;
    int left = depth(root.left);
    int right = depth(root.right);
    // 在求深度的同時判斷左右子樹是否平衡
    // 如果左子樹或右子樹不平衡，或者最大深度差大于1，則返回-1
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

參考講解：

二叉搜索樹

[98] Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree

問題：

思路：根據(jù)二叉搜索樹（BST）的性質(zhì)：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值； 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值； 它的左、右子樹也分別構(gòu)成二叉搜索樹，滿足同樣性質(zhì)。判斷一個給定的二叉樹是否為搜索二叉樹，最直觀的方法就是根據(jù)其性質(zhì)來判斷：如二叉樹[10,5,15,#,#,6,20]，如下圖所示二叉樹，對其進(jìn)行判斷的過程為：

1、對于根節(jié)點10，其左子樹節(jié)點5是否小于10，其右子樹包含節(jié)點15,6,20，需要逐一判別是否大于10；

2、如果1滿足則進(jìn)行下一步，將節(jié)點5作為根節(jié)點，按照1中的方法判斷其左子樹中的所有節(jié)點是否均小于5，其右子樹中的所有節(jié)點是否大于5；同時，將節(jié)點15作為根節(jié)點，按照1中的方法判斷其左子樹中的所有節(jié)點是否均小于15，其右子樹中的所有節(jié)點是否大于15；

3、根據(jù)上述過程，很明顯，這個判斷過程可以用“遞歸”解決，但，針對每一個根節(jié)點，我們都需要將其值與其左右子樹中的所有節(jié)點與之進(jìn)行比較，時間復(fù)雜度為O(n2).

進(jìn)一步地分析，二叉搜索樹還有一個非常重要的性質(zhì)：它的中序遍歷為遞增序列，上圖進(jìn)行中序遍歷（左，根，右）得：5,10,6,15,20，6的位置出現(xiàn)降序，因此該二叉樹不是二叉搜索樹。采用中序遍歷的思路判斷二叉搜索樹的合法性更為簡潔，一次遍歷即可完成，事件復(fù)雜度僅為O(n)。

public boolean isValidBST(TreeNode root) {
    return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean helper(TreeNode root, int left, int right) {
    if (root == null) return true;
    return root.val > left && root.val < right
            && helper(root.left, left, root.val)
            && helper(root.right, root.val, right);
}

參考講解：

[99] Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree

問題：

思路：

參考講解：

[96] Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees

問題：

思路：

參考講解：

總結(jié)

復(fù)雜度分析

時間復(fù)雜度O(n)，空間復(fù)雜度O(h)，樹的題目95%都是這樣的。

空間復(fù)雜度O(h)是因為需要考慮遞歸函數(shù)的參數(shù)所使用的空間，是存在棧上面的。空間復(fù)雜度=遞歸深度=樹的高度=O(h)=使用棧模擬遞歸所需要的空間。

三種遍歷順序的使用場景

  • 中序遍歷（BST），用一個TreeNode[1] reference wrapper keep順序的上一個節(jié)點是誰
    • BST有兩個元素?fù)Q位置了，不用額外空間的把他們換回來。
    • 樹populate 每個節(jié)點的successor pointer
    • 找tree的第x個節(jié)點(in order)
    • sorted linked list轉(zhuǎn)換成BST
  • 前序遍歷(BST)，用left bound right bound來判斷/決定位置。
    • serialize/de-serialize any binary tree（用#分割）
    • BST的serialize and deserialize
    • BST找最接近x的節(jié)點

參考資料

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容