LeetCode 总结 - 搞定 Binary Tree 面试题

题量有点多，建议Ctrl + F题号或题目哦~

二叉树的遍历（前序遍历，中序遍历，后序遍历）

[144] Binary Tree Preorder Traversal 二叉树前序遍历

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

问题：二叉树前序遍历。

思路：用一个栈来实现，由于遍历过程中要先访问树的左子树，而后右子树，所以实现的时候先把根节点的右孩子入栈，而后是左孩子。

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

问题：二叉树中序遍历。

思路：由于二叉树中序遍历要先遍历左孩子，再是根节点，最后是右孩子。所以算法先找到根节点的最左孩子，把一路下来的左孩子依次入栈，访问最左孩子，而后是访问根节点，然后把根节点右孩子当做当前节点。重复上述过程直到节点都访问完。

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为空循环结束，说明已经到达最左下节点，访问它并添加到结果
        node = stack.pop();
        results.add(node.val);
        // 把根节点右孩子当做当前节点
        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);，这样每次头插到结果中。

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);
        }
        // 自底向上层序遍历，所以每次头插到结果中
        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

问题：返回二叉树每层的最右边节点的值。

思路：

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();
            // 每次把每层的最右边一个节点的值添加到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

问题：每个节点要么有2个子节点，要么没有子节点，如果有两个子节点，这个节点的值比两个子节点都小。

思路：可以利用特性（根节点小于等于子节点的值）来加速搜索。层序遍历不停更新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==1时，需要替换根结点
    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 时，直接返回，因为添加操作已经完成，没必要遍历完剩下的结点
        if (--d == 0) return root;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 当 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类似于层序遍历中的每层的最左节点
    while (start != null) {
        TreeLinkNode cur = start;
        // cur类似于层序遍历中的一层中的各个节点
        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类似于层序遍历中每层的最左节点
    TreeLinkNode head = null;
    // prev是当前节点的前驱节点
    TreeLinkNode prev = null;
    // cur类似于层序遍历中的一层中的各个节点
    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

问题：

思路：对于二叉搜索树，公共祖先的值一定大于等于较小的节点，小于等于较大的节点。换言之，在遍历树的时候，如果当前结点大于两个节点，则结果在当前结点的左子树里，如果当前结点小于两个节点，则结果在当前节点的右子树里。
而这里不是二叉搜索树，只能用深度优先搜索，从叶子节点向上，标记子树中出现目标节点的情况。如果子树中有目标节点，标记为那个目标节点，如果没有，标记为null。显然，如果左子树、右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中找p、q的公共祖先，则必定是p本身。
换个角度，可以这么想：如果一个节点左子树有两个目标节点中的一个，右子树没有，那这个节点肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个，左子树没有，那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。
具体做法是，递归寻找两个带查询LCA的节点p和q，当找到后，返回给它们的父亲。如果某个节点的左右子树分别包括这两个节点，那么这个节点必然是所求的解，返回该节点。否则，返回左或者右子树（哪个包含p或者q的就返回哪个）。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 叶子节点左右孩子都为空，这时候返回null
    if (root == null) return null;
    // 发现目标节点则通过返回值标记该子树发现了某个目标结点
    if (root == p || root == q) return root;
    // Divide
    // 查看左子树中是否有目标结点，没有为null
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 查看右子树是否有目标节点，没有为null
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // Conquer
    // 左右节点都不为空，说明左右子树都有目标结点，则公共祖先就是本身
    if (left != null && right != null) return root;
    // 如果发现了目标节点，则继续向上标记为该目标节点
    return left == null ? right : left;
}

还有一种简单的方法是DFS分别寻找到两个节点p和q的路径，然后对比路径，查看他们的第一个分岔口，则为LCA。

参考讲解：

[404] Sum of Left Leaves

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

问题：左子叶节点之和。

思路：

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();
        // 左节点不为空且左节点是叶子结点，则把左节点的值添加到和里
        if (node.left != null && node.left.left == null && node.left.right == null) sum += node.left.val;
        // 左右子节点入栈
        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

问题：创建一个最大二叉树，创建规则是数组中的最大值为根结点，然后分隔出的左右部分再分别创建最大二叉树。

思路：

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

问题：二叉树的坡度定义为该结点的左子树之和与右子树之和的差的绝对值，求所有结点的坡度之和。

思路：后序遍历，这样就可以从叶子结点开始搜索，便于求和。

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);
    // 函数的返回值是当前根节点的值加上左右子树的和
    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值，判断二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上的值加起来刚好等于sum。

思路：树的题目基本都是用递归来解决，主要考虑两个问题：

  1. 如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和是sum减去当前结点值得路径，只要有一个存在，那么当前结点就存在路径。
  2. 考虑结束条件是什么。这里的结束条件一个是如果当前节点是空的，则返回false。另一个如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

想清楚上面两个问题，那么实现起来就是一次树的遍历，按照刚才的分析用参数或者返回值传递需要维护的值，然后按照递归条件和结束条件进行返回即可。算法的时间复杂度是一次遍历O(n)，空间复杂度是栈的大小O(logn)。

递归结束条件：
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

问题：找到所有从根节点到叶子结点的路径和为sum的路径。

思路：回溯法。其实思路和Path Sum是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量了。
具体做法是，将当前节点root的值放入list中更新sum值，判断当前节点是否满足递归条件root.left == null && root.right == null&&sum == 0。若满足，则将存有当前路径的list值存入最后的大list中，然后依次递归左子树和右子树，从存有当前路径的list中去除最后一个节点，这样便可以返回到了当前叶子节点的父节点。

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

问题：路径的定义不必从根节点开始，也不必终止与叶子节点，只需要保证从父节点指向子节点即可。

思路：我们定义一个辅助函数 path（TreeNode root，int sum），表示在以node为根节点的二叉树中，寻找包含node的路径，和为sum，返回路径的个数。该函数的返回值由三部分组成：

  1. 当前root.val是否等于sum
  2. 左子树递归
  3. 右子树递归

由于路径的根节点可以不是从该树的root节点开始，所以还需要递归计算root.left和root.right作为根节点的路径个数。

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    // 把左右节点重新看做一个根节点
    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) {
    // 递归结束条件1
    if (root == null) return;
    // 保存未进行进一步操作的字符串长度，以便后面的回溯
    int len = path.length();
    path.append(root.val).append("->");
    if (root.left == null && root.right == null) {
        // 递归结束条件2，到达叶子结点，收集路径（注意把"->"截取掉）
        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);
    }
    // 在递归调用中任何对局部变量的修改都需要回溯，以保证最上层调用者使用的局部变量和传入时的值一样
    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的路径都代表一个数字，求这些数字的和。

思路：只需在遍历过程中记录路径中的数字，在到达叶节点的时候把记录下来的数字转换成数值，加到和里面即可。递归条件是把当前的sum*10 加上子节点的值进行下一轮递归，结束条件是到子节点是空的时候就返回0。
算法的本质是一次先序遍历，所以时间是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

问题：给定一个二叉树，你需要去计算它的直径。二叉树的直径就是任意两个节点间最长的路径长度。这条路径可以通过也可以不通过根节点。注意：两个节点间的路径长度是计算的两个节点间连线的个数（也就是边的个数）。

思路：采用后序遍历即可。这道题首先很容易想到从根节点开始，分别计算左右子节点的深度然后相加即为结果，这种思路是最容易误入的。因为最长路径很可能是不经过根节点的。那么从深度优先搜索DFS的思想出发，从某一节点开始，计算以该节点为根节点的最长路径，并将其与之前的最长路径进行比较，若大于当前最长路径，则新路径为最长路径，否则之前的路径仍旧为最长路径。在计算某一节点的最长路径时，即为该节点开始左右子树的深度和。那么DFS遍历这棵二叉树的每一个节点，就可以计算出这棵二叉树两叶子节点之间的最长路径了。

面对树结构，常理采用recursion。判断左边+右边是否最长，回溯则选择最长的一边。这个问题可以分两个方面来考虑：

  1. 最长路径经过根节点：那么根节点的左子树的深度和右子树的深度就是我们的结果
  2. 最长路径没有经过根节点：这个问题就分为两个子问题，分别设置新的根节点为其左子节点和右子节点，然后重复步骤 1
private int diameter = 0;

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

// 此函数返回树的最大深度
private int helper(TreeNode root) {
    if (root == null) return 0;
    int left = helper(root.left);
    int right = helper(root.right);
    // 左子树和右子树的深度相加就是根该节点的直径
    diameter = Math.max(diameter, left + right);
    // 返回节点左右子树中较大的深度
    return Math.max(left, right) + 1;
}

参考讲解：

[687] Longest Univalue Path

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

问题：二叉树的最长路径（按边数算），路径上的每个节点的值都相同，可以不经过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

问题：二叉树的最大路径和（可以是任意两个节点）。

思路：后序遍历，因为要从叶子结点开始遍历。

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和返回的结果在本次循环中完全没有联系
    result = Math.max(result, sum);
    // 返回时只能返回路径和较大一边
    // root.val就算是负值也必须被使用
    return Math.max(left, right) + root.val;
}

参考讲解：

构建二叉树

[105] Construct Binary Tree from Preorder and Inorder Traversal

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

问题：根据前序遍历和中序遍历的结果建立二叉树。

思路：先序遍历可以直到根节点，而中序遍历可以确定该根节点的左右子树的取值范围，从而不断拆分下去，最终求解。

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的第一个元素一定是二叉树的根节点
    TreeNode root = new TreeNode(preorder[preStart]);
    // 表示在inorder中当前根节点的位置
    int inRoot = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root.val) {
            inRoot = i;
            break;
        }
    }
    // preorder中当前根节点右边一个元素一定是根节点的左孩子
    // 左孩子一定在preorder的后部分[preStart+1,end]中，inorder的前部分[inStart,inIndex-1]中
    root.left = helper(preStart + 1, inStart, inRoot - 1, preorder, inorder);
    // inorder中当前根节点右边一个元素一定是根节点的右孩子
    // 通过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

问题：根据中序遍历和后序遍历的结果建立二叉树。

思路：

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || postorder == null || inorder.length != postorder.length) return null;
    // 保存中序遍历根节点索引
    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的最后一个元素一定是二叉树的根节点
    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) {
    // 如果当前结点不存在，直接返回
    if (t == null) return;
    // 在当前结点值前面加上左括号
    sb.append("(" + t.val);
    // 如果左子结点不存在而右子结点存在，要在结果 sb 后加上个空括号
    if (t.left == null && t.right != null) sb.append("()");
    // 分别对左右子结点调用递归函数
    helper(t.left, sb);
    helper(t.right, sb);
    // 调用完之后要加上右括号，形成封闭的括号
    sb.append(")");
}

参考讲解：

二叉树的性质

[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

问题：

思路：当求最大深度时，我们只要在左右子树中取较大的就行了，然而最小深度时，如果左右子树中有一个为空会返回0，这时我们是不能算做有效深度的。
所以分成了三种情况，左子树为空，右子树为空，左右子树都不为空。当然，如果左右子树都为空的话，就会返回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

问题：

思路：根据题目中的描述可知，这里的最大宽度不是满树的时候的最大宽度，如果是那样的话，肯定是最后一层的结点数最多。这里的最大宽度应该是两个存在的结点中间可容纳的总的结点个数，中间的结点可以为空。我们可以根据左子树节点是根节点的2倍来做。

public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int result = 0;
    // 用于树的广度优先遍历
    Queue<TreeNode> queue = new LinkedList<>();
    // 用于保存上面队列中树节点对应的位置标号
    Queue<Integer> queuePos = new LinkedList<>();
    queue.offer(root);
    // 在顶层跟结点位置为1
    queuePos.add(1);
    // 首先判断此队列是否为空
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 每一层中第一个节点的下标
        int start = queuePos.peek();
        // 每一层中最大孩子的位置下标
        int end = start;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            end = queuePos.poll();
            // 从左子树头节点开始，走到最后一个节点
            if (node.left != null) {
                queue.offer(node.left);
                // 左孩子的下标
                queuePos.offer(2 * end);
            }
            // 从右子树头节点开始，走到最后一个节点
            if (node.right != null) {
                queue.offer(node.right);
                // 右孩子的下标
                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的根结点开始，跟t比较，如果两棵树完全相同，那么返回true。否则就分别对s的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回true了，就表示可以找得到。

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    // 先从s的根结点开始，跟t比较，如果两棵树完全相同，那么返回true
    if (isSameTree(s, t)) return true;
    // 否则就分别对 s 的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回 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

问题：

思路：递归地把左子树和右子树取出来，再进行调换。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
    // 将当前节点的左右分支进行对调反转
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    // 若左分支存在，则递归左分支的节点
    if (root.left != null) invertTree(root.left);
    // 若右分支存在，则递归右分支的节点
    if (root.right != null) invertTree(root.right);
    // 所有的节点遍历完成后，返回根节点
    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）。

思路：以当前节点为根节点判断高度差，再以左右子节点为根节点进行判断。

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

问题：

思路：根据二叉搜索树（BST）的性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别构成二叉搜索树，满足同样性质。判断一个给定的二叉树是否为搜索二叉树，最直观的方法就是根据其性质来判断：如二叉树[10,5,15,#,#,6,20]，如下图所示二叉树，对其进行判断的过程为：

1、对于根节点10，其左子树节点5是否小于10，其右子树包含节点15,6,20，需要逐一判别是否大于10；

2、如果1满足则进行下一步，将节点5作为根节点，按照1中的方法判断其左子树中的所有节点是否均小于5，其右子树中的所有节点是否大于5；同时，将节点15作为根节点，按照1中的方法判断其左子树中的所有节点是否均小于15，其右子树中的所有节点是否大于15；

3、根据上述过程，很明显，这个判断过程可以用“递归”解决，但，针对每一个根节点，我们都需要将其值与其左右子树中的所有节点与之进行比较，时间复杂度为O(n2).

进一步地分析，二叉搜索树还有一个非常重要的性质：它的中序遍历为递增序列，上图进行中序遍历（左，根，右）得：5,10,6,15,20，6的位置出现降序，因此该二叉树不是二叉搜索树。采用中序遍历的思路判断二叉搜索树的合法性更为简洁，一次遍历即可完成，事件复杂度仅为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

问题：

思路：

参考讲解：

总结

复杂度分析

时间复杂度O(n)，空间复杂度O(h)，树的题目95%都是这样的。

空间复杂度O(h)是因为需要考虑递归函数的参数所使用的空间，是存在栈上面的。空间复杂度=递归深度=树的高度=O(h)=使用栈模拟递归所需要的空间。

三种遍历顺序的使用场景

  • 中序遍历（BST），用一个TreeNode[1] reference wrapper keep顺序的上一个节点是谁
    • BST有两个元素换位置了，不用额外空间的把他们换回来。
    • 树populate 每个节点的successor pointer
    • 找tree的第x个节点(in order)
    • sorted linked list转换成BST
  • 前序遍历(BST)，用left bound right bound来判断/决定位置。
    • serialize/de-serialize any binary tree（用#分割）
    • BST的serialize and deserialize
    • BST找最接近x的节点

参考资料

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,271评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,275评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,151评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,550评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,553评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,559评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,924评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,580评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,826评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,578评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,661评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,363评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,940评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,926评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,156评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,872评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,391评论 2赞 342