[关闭]
@Yano 2019-09-20T10:54:55.000000Z 字数 21953 阅读 4627

LeetCode 二叉树经典题目

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

说明

二叉树的题目，主要有一下几种：
1. 前中后序遍历、根据前序遍历和中序遍历构造二叉树、根据中序遍历和后序遍历构造二叉树；
2. BST：查找第k大的数
3. LCA：最近公共祖先
4. 层序遍历
5. 扩展树
6. 序列化、反序列化二叉树

大部分题目使用DFS会更简洁。这篇文章并没有区分节点和结点，因为我也不知道用哪个……

题目并不在于多，我把LeetCode上部分相似的题目列出来，大家通过对比观察相似题目，就能够触类旁通。其实90%的题目都是差不多的，只是换了不同的问法而已。

题目

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

递归

  1. public class Solution {
  3.     public void robot(TreeNode p, List<Integer> ans) {
  4.         if(p == null) return;
  5.         // 中左右
  6.         ans.add(p.val);
  7.         robot(p.left, ans);
  8.         robot(p.right, ans);
  9.     }
  11.     public List<Integer> preorderTraversal(TreeNode root) {
  12.         List<Integer> ans = new ArrayList<Integer>();
  13.         robot(root, ans);
  14.         return ans;
  15.     }
  16. }

非递归

拿出并访问一个结点，将左右结点放入。

  1. public class Solution {
  3.     public List<Integer> preorderTraversal(TreeNode root) {
  4.         List<Integer> ans = new ArrayList<Integer>();
  6.         List<TreeNode> vector = new ArrayList<TreeNode>();
  7.         vector.add(root);
  8.         while(vector.size() != 0){
  9.             TreeNode r = vector.get(vector.size() - 1);
  10.             vector.remove(vector.size() - 1);
  11.             if(r != null) {
  12.                 ans.add(r.val);
  13.                 vector.add(r.right);
  14.                 vector.add(r.left);
  15.             }
  16.         }
  18.         return ans;
  19.     }
  20. }

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

递归

  1. public class Solution {
  3.     public void robot(TreeNode p, List<Integer> ans) {
  4.         if(p == null) return;
  5.         // 左中右
  6.         robot(p.left, ans);
  7.         ans.add(p.val);
  8.         robot(p.right, ans);
  9.     }
  11.     public List<Integer> inorderTraversal(TreeNode root) {
  12.         List<Integer> ans = new ArrayList<Integer>();
  13.         robot(root, ans);
  14.         return ans;
  15.     }
  16. }

非递归

  1. public class Solution {
  3.     public List<Integer> inorderTraversal(TreeNode r) {
  4.         List<Integer> ans = new ArrayList<Integer>();
  6.         List<TreeNode> vector = new ArrayList<TreeNode>();
  7.         while(vector.size() != 0 || r != null){
  9.             // 一直放入左儿子（左）
  10.             while(r != null) {
  11.                 vector.add(r);
  12.                 r = r.left;
  13.             }
  15.             // 访问当前元素（中），把右儿子入栈（右）
  16.             if(vector.size() != 0) {
  17.                 r = vector.get(vector.size() - 1);
  18.                 vector.remove(vector.size() - 1);
  19.                 ans.add(r.val);
  20.                 r = r.right;
  21.             }
  22.         }
  24.         return ans;
  25.     }
  26. }

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

递归

  1. public class Solution {
  2.      public void robot(TreeNode p, List<Integer> ans) {
  3.         if(p == null) return;
  4.         // 左右中
  5.         robot(p.left, ans);
  6.         robot(p.right, ans);
  7.         ans.add(p.val);
  8.     }
  9.     public List<Integer> postorderTraversal(TreeNode root) {
  10.         List<Integer> ans = new ArrayList<Integer>();
  11.         robot(root, ans);
  12.         return ans;
  13.     }
  14. }

非递归

后序遍历的非递归写法有些麻烦，因为结点第一次访问时并不打印，而是在第二次遍历时才打印。所以需要一个变量来标记该结点是否访问过。

  1. public class Solution {
  3.     public static class StackNode {
  4.         TreeNode r;
  5.         boolean isFirst;
  6.         StackNode(TreeNode r, boolean isFirst) {
  7.             this.r = r;
  8.             this.isFirst = isFirst;
  9.         }
  10.     }
  11.     public List<Integer> postorderTraversal(TreeNode r) {
  12.         List<Integer> ans = new ArrayList<Integer>();
  14.         List<StackNode> vector = new ArrayList<StackNode>();
  15.         StackNode node;
  16.         while(vector.size() != 0 || r != null){
  18.             // 一直放入左儿子（左）
  19.             while(r != null) {
  20.                 node = new StackNode(r, true);
  21.                 vector.add(node);
  22.                 r = r.left;
  23.             }
  25.             // 把右儿子入栈（右），访问当前元素（中）
  26.             if(vector.size() != 0) {
  27.                 node = vector.get(vector.size() - 1);
  28.                 vector.remove(vector.size() - 1);
  30.                 // 首次访问，再次入栈，并置状态
  31.                 if(node.isFirst) {
  32.                     node.isFirst = false;
  33.                     vector.add(node);
  34.                     r = node.r.right;
  35.                 } else {
  36.                     ans.add(node.r.val);
  37.                     r = null;
  38.                 }
  39.             }
  40.         }
  42.         return ans;
  43.     }
  44. }

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

思路：ans的第k个元素，存储第k层的答案，在遍历的过程中记录答案。原型就是前序遍历。

  1. public class Solution {
  3.     public void robot(List<List<Integer>> ans, TreeNode root, int height) {
  4.         if(root == null) return;
  5.         if(height >= ans.size()){
  6.             ans.add(new ArrayList<Integer>());
  7.         }
  9.         ans.get(height).add(root.val);
  10.         robot(ans, root.left, height + 1);
  11.         robot(ans, root.right, height + 1);
  12.     }
  14.     public List<List<Integer>> levelOrder(TreeNode root) {
  15.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  16.         robot(ans, root, 0);
  17.         return ans;
  18.     }
  19. }

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路：和上一题是一样的，要么在遍历的过程中，将偶数层反转；要么在结束的时候，将偶数层反转。

  1. public class Solution {
  2.     public void robot(List<List<Integer>> ans, TreeNode root, int height) {
  3.         if(root == null) return;
  4.         if(height >= ans.size()){
  5.             ans.add(new ArrayList<Integer>());
  6.         }
  8.         ans.get(height).add(root.val);
  9.         robot(ans, root.left, height + 1);
  10.         robot(ans, root.right, height + 1);
  11.     }
  13.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  14.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  15.         robot(ans, root, 0);
  16.         for(int i = 0; i < ans.size(); i++) {
  17.             if(i % 2 != 0) {
  18.                 Collections.reverse(ans.get(i));
  19.             }
  20.         }
  21.         return ans;
  22.     }
  23. }

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

思路：这道题其实也是层序遍历，和前两道题一模一样，只不过要记录的不是每层所有的结果，只需要记录每层的最后一个结果！

  1. public class Solution {
  3.     public void robot(TreeNode root, List<Integer> ans, int height) {
  4.         if(root == null) return;
  5.         if(ans.size() <= height) {
  6.             ans.add(0);
  7.         }
  8.         ans.set(height, root.val);
  9.         robot(root.left, ans, height + 1);
  10.         robot(root.right, ans, height + 1);
  11.     }
  13.     public List<Integer> rightSideView(TreeNode root) {
  14.         List<Integer> ans = new ArrayList<Integer>();
  15.         robot(root, ans, 0);
  16.         return ans;
  17.     }
  18. }

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：论坛上的一个答案

The basic idea is here:
- Say we have 2 arrays, PRE and IN.
- Preorder traversing implies that PRE[0] is the root node.
- Then we can find this PRE[0] in IN, say it's IN[5].
- Now we know that IN[5] is root, so we know that IN[0] - IN[4] is on the left side, IN[6] to the end is on the right side.
- Recursively doing this on subarrays, we can build a tree out of it :)

  1. public class Solution {
  3.     TreeNode build(int preStart, int inStart, int inEnd, int[] pre, int[] in) {
  4.         if(preStart >= pre.length || inStart > inEnd) {
  5.             return null;
  6.         }
  7.         TreeNode root = new TreeNode(pre[preStart]);
  9.         int inIndex = 0;
  10.         for(int i = inStart; i <= inEnd; i++) {
  11.             if(in[i] == root.val) {
  12.                 inIndex = i;
  13.                 break;
  14.             }
  15.         }
  17.         root.left = build(preStart + 1, inStart, inIndex - 1, pre, in);
  18.         root.right = build(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, pre, in);
  19.         return root;
  20.     }
  22.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  23.         TreeNode root = build(0, 0, inorder.length - 1, preorder, inorder);
  24.         return root;
  25.     }
  26. }

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

  1. public class Solution {
  3.     public TreeNode robot(int poStart, int poEnd, int inStart, int inEnd, int[] in, int[] po) {
  4.         if(poStart > poEnd) {
  5.             return null;
  6.         }
  8.         TreeNode root = new TreeNode(po[poEnd]);
  9.         int index = 0;
  10.         for(int i = inStart; i <= inEnd; i++) {
  11.             if(in[i] == root.val) {
  12.                 index = i;
  13.                 break;
  14.             }
  15.         }
  17.         root.left = robot(poStart, poStart + index - inStart - 1 , inStart, index - 1, in, po);
  18.         root.right = robot(poEnd - inEnd + index, poEnd - 1, index + 1, inEnd, in, po);
  20.         return root;
  21.     }
  23.     public TreeNode buildTree(int[] in, int[] po) {
  24.         TreeNode root = robot(0, po.length - 1, 0, in.length - 1, in, po);
  25.         return root;
  26.     }
  27. }

95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路：首先确定根节点，然后确定左子树和右子树。注意同一个数作为根节点时，可能有多个不同的子树。

  1. public class Solution {
  3.     public List<TreeNode> robot(int start, int end) {
  4.         List<TreeNode> ans = new ArrayList<TreeNode>();
  6.         if(start > end) {
  7.             ans.add(null);
  8.             return ans;
  9.         }
  11.         if(start == end) {
  12.             ans.add(new TreeNode(start));
  13.             return ans;
  14.         }
  16.         for(int i = start; i <= end; i++) {
  17.             List<TreeNode> leftList = robot(start, i - 1);
  18.             List<TreeNode> rightList = robot(i + 1, end);
  19.             for(TreeNode left : leftList) {
  20.                 for(TreeNode right : rightList) {
  21.                     TreeNode root = new TreeNode(i);
  22.                     root.left = left;
  23.                     root.right = right;
  24.                     ans.add(root);
  25.                 }
  26.             }    
  27.         }
  29.         return ans;
  30.     }
  32.     public List<TreeNode> generateTrees(int n) {
  33.         if(n == 0) return new ArrayList<TreeNode>();
  34.         return robot(1, n);
  35.     }
  36. }

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路：设f(n)代表构造出的树的个数。那么：

f(n) = f(n-1)f(0) + f(n-2)f(1) + ... + f(0)f(n-1)

  1. public class Solution {
  2.     public int numTrees(int n) {
  3.         if(n <= 0) return 0;
  4.         int[] dp = new int[n + 1];
  5.         dp[0] = dp[1] = 1;
  6.         for(int i = 2; i <= n; i++) {
  7.             for(int j = 1; j <= i; j++) {
  8.                 dp[i] += dp[j - 1] * dp[i - j];
  9.             }
  10.         }
  11.         return dp[n];
  12.     }
  13. }

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.
Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

  1. public class Solution {
  3.     public boolean robot(TreeNode root, long min, long max) {
  4.         if(root == null) return true;
  5.         if(root.val >= max || root.val <= min) return false;
  6.         return robot(root.left, min, root.val) && robot(root.right, root.val, max);
  7.     }
  9.     public boolean isValidBST(TreeNode root) {
  10.         return robot(root, Long.MIN_VALUE, Long.MAX_VALUE);
  11.     }
  12. }

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

  1. public class Solution {
  3.     public boolean robot(TreeNode p, TreeNode q) {
  4.         if(p == null && q == null) {
  5.             return true;
  6.         }
  7.         if(p != null && q != null && p.val == q.val) {
  8.             return robot(p.left, q.left) && robot(p.right, q.right);
  9.         }
  10.         return false;
  11.     }
  13.     public boolean isSameTree(TreeNode p, TreeNode q) {
  14.         return robot(p, q);
  15.     }
  16. }

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

  1. public class Solution {
  3.     public boolean robot(TreeNode p, TreeNode q) {
  4.         if(p == null && q == null) {
  5.             return true;
  6.         }
  7.         if(p != null && q != null && p.val == q.val) {
  8.             return robot(p.left, q.right) && robot(p.right, q.left);
  9.         }
  10.         return false;
  11.     }
  13.     public boolean isSymmetric(TreeNode root) {
  14.         if(root == null) return true;
  15.         return robot(root.left, root.right);
  16.     }
  17. }

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

  1. public class Solution {
  3.     public int robot(TreeNode root, int depth) {
  4.         if(root == null) return depth;
  5.         return Math.max(robot(root.left, depth + 1), robot(root.right, depth + 1));
  6.     }
  8.     public int maxDepth(TreeNode root) {
  9.         return robot(root, 0);
  10.     }
  11. }

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

  1. public class Solution {
  3.     public int depth(TreeNode root) {
  4.         if(root == null) return 0;
  5.         return Math.max(depth(root.left), depth(root.right)) + 1;
  6.     }
  8.     public boolean isBalanced(TreeNode root) {
  9.         if(root == null) return true;
  11.         int left = depth(root.left);
  12.         int right = depth(root.right);
  14.         return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  15.     }
  16. }

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

  1. public class Solution {
  3.     public int minDepth(TreeNode root) {
  4.         if(root == null) return 0;
  5.         int left = minDepth(root.left);
  6.         int right = minDepth(root.right);
  7.         return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1;
  8.     }
  9. }

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

  1. public class Solution {
  3.     public boolean hasPathSum(TreeNode root, int sum) {
  4.         if(root == null) return false;
  5.         int left = sum - root.val;
  6.         if(root.left == null && root.right == null && left == 0) {
  7.             return true;
  8.         }
  9.         return hasPathSum(root.left, left) || hasPathSum(root.right, left);
  10.     }
  11. }

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

思路：和上一道题是一样的，只不过这次需要保存结果。

  1. public class Solution {
  3.     public void robot(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> tmp) {
  4.         if(root == null) return;
  5.         if(root.left == null && root.right == null && sum - root.val == 0) {
  6.             tmp.add(root.val);
  7.             ans.add(new ArrayList(tmp));
  8.             tmp.remove(tmp.size() - 1);
  9.             return;
  10.         }
  11.         tmp.add(root.val);
  12.         robot(root.left, sum - root.val, ans, tmp);
  13.         robot(root.right, sum - root.val, ans, tmp);
  14.         tmp.remove(tmp.size() - 1);
  15.     }
  17.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  18.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  19.         List<Integer> tmp = new ArrayList<Integer>();
  20.         robot(root, sum, ans, tmp);
  21.         return ans;
  22.     }
  23. }

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

  1. public class Solution {
  3.     public int robot(TreeNode root, int sum) {
  4.         if(root == null) return 0;
  5.         if(root.left == null && root.right == null) {
  6.             return sum * 10 + root.val;
  7.         }
  8.         return robot(root.left, sum * 10 + root.val) + robot(root.right, sum * 10 + root.val);
  9.     }
  11.     public int sumNumbers(TreeNode root) {
  12.         return robot(root, 0);
  13.     }
  14. }

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

思路：这个题和上面的题是一样的，只不过上面的题求根节点到叶子节点的和，而这道题是把路径用字符串表示出来。

  1. public class Solution {
  3.     public void robot(TreeNode root, String path, List<String> ans) {
  4.         if(root.left == null && root.right == null) {
  5.             ans.add(path + root.val);
  6.             return;
  7.         }
  8.         if(root.left != null) robot(root.left, path + root.val + "->", ans);
  9.         if(root.right != null) robot(root.right, path + root.val + "->", ans);
  10.     }
  12.     public List<String> binaryTreePaths(TreeNode root) {
  13.         List<String> ans = new ArrayList<String>();
  14.         if(root != null) {
  15.             robot(root, "", ans);
  16.         }
  17.         return ans;
  18.     }
  19. }

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

  1. public class Solution {
  3.     public TreeNode robot(int[] nums, int start, int end) {
  4.         if(start > end) return null;
  5.         int mid = (start + end) / 2;
  6.         TreeNode root = new TreeNode(nums[mid]);
  7.         // 已经是排序数组，所以只要找中点即可
  8.         root.left = robot(nums, start, mid - 1);
  9.         root.right = robot(nums, mid + 1, end);
  10.         return root;
  11.     }
  13.     public TreeNode sortedArrayToBST(int[] nums) {
  14.         // 二分，才会「高度平衡」
  15.         if(nums.length == 0) return null;
  16.         return robot(nums, 0, nums.length - 1);
  17.     }
  18. }

116. Populating Next Right Pointers in Each Node

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

     1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

  1. public class Solution {
  3.     public void connect(TreeLinkNode root) {
  4.        if(root == null) return;
  5.        if(root.left != null) {
  6.            root.left.next = root.right;
  7.            if(root.right != null && root.next != null) {
  8.                root.right.next = root.next.left;
  9.            }
  10.        }
  12.        connect(root.left);
  13.        connect(root.right);
  14.     }
  15. }

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

思路：相当于二分查找，并不需要挨个遍历每个节点。只要从某一节点开始，到左叶子结点和到右叶子结点的长度相同，就可以利用性质计算出结点个数。

  1. public class Solution {
  2.     public int countNodes(TreeNode root) {
  3.         if(root == null) return 0;
  5.         int left = leftHeight(root);
  6.         int right = rightHeight(root);
  8.         if(left == right) {
  9.             return (1 << left) - 1;
  10.         }
  12.         return 1 + countNodes(root.left) + countNodes(root.right);
  13.     }
  15.     public int leftHeight(TreeNode root) {
  16.         int depth = 0;
  17.         while(root != null) {
  18.             root = root.left;
  19.             depth++;
  20.         }
  21.         return depth;
  22.     }
  24.     public int rightHeight(TreeNode root) {
  25.         int depth = 0;
  26.         while(root != null) {
  27.             root = root.right;
  28.             depth++;
  29.         }
  30.         return depth;
  31.     }
  32. }

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

  1. public class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root == null) return root;
  4.         TreeNode tmp = root.left;
  5.         root.left = root.right;
  6.         root.right = tmp;
  7.         invertTree(root.left);
  8.         invertTree(root.right);
  9.         return root;
  10.     }
  11. }

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ? k ? BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路：利用BST的性质，前序遍历的第k个数，即为第k大的数。

  1. public class Solution {
  3.     private static int number = 0; // 最终结果
  4.     private static int count = 0;
  6.     public void robot(TreeNode r) {
  7.         if(r.left != null) robot(r.left);
  9.         count--;
  10.         if(count == 0) {
  11.             number = r.val;
  12.             return;
  13.         }
  15.         if(r.right != null) robot(r.right);
  16.     }
  18.     // 中序遍历，第k个数
  19.     public int kthSmallest(TreeNode root, int k) {
  20.         count = k;
  21.         robot(root);
  22.         return number;
  23.     }
  24. }

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

思路：利用BST的性质，LCA是最后一个值介于两个节点之间的节点。

  1. public class Solution {
  2.     public static TreeNode ans = null;
  4.     public void robot(TreeNode root, int min, int max) {
  5.         if(root == null) return;
  6.         robot(root.left, min, max);
  7.         if(root.val >= min && root.val <= max) {
  8.             ans = root;
  9.             return;
  10.         }
  11.         robot(root.right, min, max);
  12.     }
  14.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  15.         // 中序遍历，找介于p和q之间的node
  16.         if(root == null || p == null || q == null) return null;
  17.         int min = Math.min(p.val, q.val);
  18.         int max = Math.max(p.val, q.val);
  19.         robot(root, min, max);
  20.         return ans;
  21.     }
  22. }

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路：这道题比上一道题更进一步，去掉了BST的特殊条件。可以分为两种情况：
- 左右结点并不互为父子节点
- 左右结点互为父子节点

  1. public class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root == null || root == p || root == q) {
  4.             return root;
  5.         }
  6.         TreeNode left = lowestCommonAncestor(root.left, p, q);
  7.         TreeNode right = lowestCommonAncestor(root.right, p, q);
  8.         if(left != null && right != null) return root;
  9.         return left == null ? right : left;
  10.     }
  11. }

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Codec {
  12.     // Encodes a tree to a single string.
  13.     public String serialize(TreeNode root) {
  14.         StringBuilder sb = new StringBuilder();
  15.         robot(root, sb);
  16.         return sb.toString();
  17.     }
  19.     public void robot(TreeNode root, StringBuilder sb) {
  20.         if(root == null) {
  21.             sb.append("X").append(",");
  22.         } else {
  23.             sb.append(root.val + "").append(",");
  24.             robot(root.left, sb);
  25.             robot(root.right, sb);
  26.         }
  27.     }
  29.     // Decodes your encoded data to tree.
  30.     public TreeNode deserialize(String data) {
  31.         Deque<String> nodes = new LinkedList<>();
  32.         nodes.addAll(Arrays.asList(data.split(",")));
  33.         return buildTree(nodes);
  34.     }
  36.     public TreeNode buildTree(Deque<String> nodes) {
  37.         String val = nodes.remove();
  38.         if(val.equals("X")) {
  39.             return null;
  40.         } else {
  41.             TreeNode root = new TreeNode(Integer.valueOf(val));
  42.             root.left = buildTree(nodes);
  43.             root.right = buildTree(nodes);
  44.             return root;
  45.         }
  46.     }
  47. }
  49. // Your Codec object will be instantiated and called as such:
  50. // Codec codec = new Codec();
  51. // codec.deserialize(codec.serialize(root));

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

思路：实际上是动态规划，当前结点分为两种情况：
- 抢该结点，那么子节点就不能抢；
- 不抢该结点，那么子节点可以抢，也可以不抢。

  1. public class Solution {
  3.     public int rob(TreeNode root) {
  4.         if(root == null) return 0;
  5.         return Math.max(robIn(root), robEx(root));
  6.     }
  8.     public int robIn(TreeNode root) {
  9.         if(root == null) return 0;
  10.         return robEx(root.left) + robEx(root.right) + root.val;
  11.     }
  13.     public int robEx(TreeNode root) {
  14.         if(root == null) return 0;
  15.         return rob(root.left) + rob(root.right);
  16.     }
  17. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注