目錄
簡書的 markdown 都不支持 [TOC] 語法……我就不貼目錄了姚炕。下面按照類別摊欠，列出了29道關(guān)于二叉樹的題目丢烘。認真看會發(fā)現(xiàn)，其實題目核心思想都是DFS（如果使用的話）些椒，并且題目的類型并不多播瞳。
說明
二叉樹的題目，主要有一下幾種：
- 前中后序遍歷免糕、根據(jù)前序遍歷和中序遍歷構(gòu)造二叉樹赢乓、根據(jù)中序遍歷和后序遍歷構(gòu)造二叉樹；
- BST：查找第k大的數(shù)
- LCA：最近公共祖先
- 層序遍歷
- 擴展樹
- 序列化石窑、反序列化二叉樹
大部分題目使用DFS會更簡潔牌芋。這篇文章并沒有區(qū)分節(jié)點和結(jié)點，因為我也不知道用哪個……
題目并不在于多松逊，我把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?
遞歸
public class Solution {
public void robot(TreeNode p, List<Integer> ans) {
if(p == null) return;
// 中左右
ans.add(p.val);
robot(p.left, ans);
robot(p.right, ans);
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
robot(root, ans);
return ans;
}
}
非遞歸
拿出并訪問一個結(jié)點烁兰，將左右結(jié)點放入耐亏。
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
List<TreeNode> vector = new ArrayList<TreeNode>();
vector.add(root);
while(vector.size() != 0){
TreeNode r = vector.get(vector.size() - 1);
vector.remove(vector.size() - 1);
if(r != null) {
ans.add(r.val);
vector.add(r.right);
vector.add(r.left);
}
}
return ans;
}
}
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?
遞歸
public class Solution {
public void robot(TreeNode p, List<Integer> ans) {
if(p == null) return;
// 左中右
robot(p.left, ans);
ans.add(p.val);
robot(p.right, ans);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
robot(root, ans);
return ans;
}
}
非遞歸
public class Solution {
public List<Integer> inorderTraversal(TreeNode r) {
List<Integer> ans = new ArrayList<Integer>();
List<TreeNode> vector = new ArrayList<TreeNode>();
while(vector.size() != 0 || r != null){
// 一直放入左兒子（左）
while(r != null) {
vector.add(r);
r = r.left;
}
// 訪問當(dāng)前元素（中），把右兒子入棧（右）
if(vector.size() != 0) {
r = vector.get(vector.size() - 1);
vector.remove(vector.size() - 1);
ans.add(r.val);
r = r.right;
}
}
return ans;
}
}
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?
遞歸
public class Solution {
public void robot(TreeNode p, List<Integer> ans) {
if(p == null) return;
// 左右中
robot(p.left, ans);
robot(p.right, ans);
ans.add(p.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
robot(root, ans);
return ans;
}
}
非遞歸
后序遍歷的非遞歸寫法有些麻煩沪斟，因為結(jié)點第一次訪問時并不打印广辰，而是在第二次遍歷時才打印。所以需要一個變量來標(biāo)記該結(jié)點是否訪問過主之。
public class Solution {
public static class StackNode {
TreeNode r;
boolean isFirst;
StackNode(TreeNode r, boolean isFirst) {
this.r = r;
this.isFirst = isFirst;
}
}
public List<Integer> postorderTraversal(TreeNode r) {
List<Integer> ans = new ArrayList<Integer>();
List<StackNode> vector = new ArrayList<StackNode>();
StackNode node;
while(vector.size() != 0 || r != null){
// 一直放入左兒子（左）
while(r != null) {
node = new StackNode(r, true);
vector.add(node);
r = r.left;
}
// 把右兒子入棧（右）轨域，訪問當(dāng)前元素（中）
if(vector.size() != 0) {
node = vector.get(vector.size() - 1);
vector.remove(vector.size() - 1);
// 首次訪問，再次入棧杀餐，并置狀態(tài)
if(node.isFirst) {
node.isFirst = false;
vector.add(node);
r = node.r.right;
} else {
ans.add(node.r.val);
r = null;
}
}
}
return ans;
}
}
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層的答案，在遍歷的過程中記錄答案史翘。原型就是前序遍歷枉长。
public class Solution {
public void robot(List<List<Integer>> ans, TreeNode root, int height) {
if(root == null) return;
if(height >= ans.size()){
ans.add(new ArrayList<Integer>());
}
ans.get(height).add(root.val);
robot(ans, root.left, height + 1);
robot(ans, root.right, height + 1);
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
robot(ans, root, 0);
return ans;
}
}
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]
]
思路：和上一題是一樣的冀续，要么在遍歷的過程中，將偶數(shù)層反轉(zhuǎn)必峰；要么在結(jié)束的時候洪唐，將偶數(shù)層反轉(zhuǎn)。
public class Solution {
public void robot(List<List<Integer>> ans, TreeNode root, int height) {
if(root == null) return;
if(height >= ans.size()){
ans.add(new ArrayList<Integer>());
}
ans.get(height).add(root.val);
robot(ans, root.left, height + 1);
robot(ans, root.right, height + 1);
}
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
robot(ans, root, 0);
for(int i = 0; i < ans.size(); i++) {
if(i % 2 != 0) {
Collections.reverse(ans.get(i));
}
}
return ans;
}
}
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].
思路：這道題其實也是層序遍歷吼蚁，和前兩道題一模一樣凭需，只不過要記錄的不是每層所有的結(jié)果，只需要記錄每層的最后一個結(jié)果肝匆！
public class Solution {
public void robot(TreeNode root, List<Integer> ans, int height) {
if(root == null) return;
if(ans.size() <= height) {
ans.add(0);
}
ans.set(height, root.val);
robot(root.left, ans, height + 1);
robot(root.right, ans, height + 1);
}
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
robot(root, ans, 0);
return ans;
}
}
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 :)
public class Solution {
TreeNode build(int preStart, int inStart, int inEnd, int[] pre, int[] in) {
if(preStart >= pre.length || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
int inIndex = 0;
for(int i = inStart; i <= inEnd; i++) {
if(in[i] == root.val) {
inIndex = i;
break;
}
}
root.left = build(preStart + 1, inStart, inIndex - 1, pre, in);
root.right = build(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, pre, in);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
TreeNode root = build(0, 0, inorder.length - 1, preorder, inorder);
return root;
}
}
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.
public class Solution {
public TreeNode robot(int poStart, int poEnd, int inStart, int inEnd, int[] in, int[] po) {
if(poStart > poEnd) {
return null;
}
TreeNode root = new TreeNode(po[poEnd]);
int index = 0;
for(int i = inStart; i <= inEnd; i++) {
if(in[i] == root.val) {
index = i;
break;
}
}
root.left = robot(poStart, poStart + index - inStart - 1 , inStart, index - 1, in, po);
root.right = robot(poEnd - inEnd + index, poEnd - 1, index + 1, inEnd, in, po);
return root;
}
public TreeNode buildTree(int[] in, int[] po) {
TreeNode root = robot(0, po.length - 1, 0, in.length - 1, in, po);
return root;
}
}
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
思路：首先確定根節(jié)點粒蜈，然后確定左子樹和右子樹。注意同一個數(shù)作為根節(jié)點時旗国，可能有多個不同的子樹枯怖。
public class Solution {
public List<TreeNode> robot(int start, int end) {
List<TreeNode> ans = new ArrayList<TreeNode>();
if(start > end) {
ans.add(null);
return ans;
}
if(start == end) {
ans.add(new TreeNode(start));
return ans;
}
for(int i = start; i <= end; i++) {
List<TreeNode> leftList = robot(start, i - 1);
List<TreeNode> rightList = robot(i + 1, end);
for(TreeNode left : leftList) {
for(TreeNode right : rightList) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
ans.add(root);
}
}
}
return ans;
}
public List<TreeNode> generateTrees(int n) {
if(n == 0) return new ArrayList<TreeNode>();
return robot(1, n);
}
}
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
思路：設(shè)f(n)代表構(gòu)造出的樹的個數(shù)。那么：
f(n) = f(n-1)f(0) + f(n-2)f(1) + ... + f(0)f(n-1)
public class Solution {
public int numTrees(int n) {
if(n <= 0) return 0;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
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.
public class Solution {
public boolean robot(TreeNode root, long min, long max) {
if(root == null) return true;
if(root.val >= max || root.val <= min) return false;
return robot(root.left, min, root.val) && robot(root.right, root.val, max);
}
public boolean isValidBST(TreeNode root) {
return robot(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
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.
public class Solution {
public boolean robot(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p != null && q != null && p.val == q.val) {
return robot(p.left, q.left) && robot(p.right, q.right);
}
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
return robot(p, q);
}
}
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.
public class Solution {
public boolean robot(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p != null && q != null && p.val == q.val) {
return robot(p.left, q.right) && robot(p.right, q.left);
}
return false;
}
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return robot(root.left, root.right);
}
}
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.
public class Solution {
public int robot(TreeNode root, int depth) {
if(root == null) return depth;
return Math.max(robot(root.left, depth + 1), robot(root.right, depth + 1));
}
public int maxDepth(TreeNode root) {
return robot(root, 0);
}
}
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.
public class Solution {
public int depth(TreeNode root) {
if(root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
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);
}
}
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.
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1;
}
}
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.
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) return false;
int left = sum - root.val;
if(root.left == null && root.right == null && left == 0) {
return true;
}
return hasPathSum(root.left, left) || hasPathSum(root.right, left);
}
}
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]
]
思路：和上一道題是一樣的能曾，只不過這次需要保存結(jié)果度硝。
public class Solution {
public void robot(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> tmp) {
if(root == null) return;
if(root.left == null && root.right == null && sum - root.val == 0) {
tmp.add(root.val);
ans.add(new ArrayList(tmp));
tmp.remove(tmp.size() - 1);
return;
}
tmp.add(root.val);
robot(root.left, sum - root.val, ans, tmp);
robot(root.right, sum - root.val, ans, tmp);
tmp.remove(tmp.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> tmp = new ArrayList<Integer>();
robot(root, sum, ans, tmp);
return ans;
}
}
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.
public class Solution {
public int robot(TreeNode root, int sum) {
if(root == null) return 0;
if(root.left == null && root.right == null) {
return sum * 10 + root.val;
}
return robot(root.left, sum * 10 + root.val) + robot(root.right, sum * 10 + root.val);
}
public int sumNumbers(TreeNode root) {
return robot(root, 0);
}
}
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"]
思路：這個題和上面的題是一樣的，只不過上面的題求根節(jié)點到葉子節(jié)點的和寿冕，而這道題是把路徑用字符串表示出來蕊程。
public class Solution {
public void robot(TreeNode root, String path, List<String> ans) {
if(root.left == null && root.right == null) {
ans.add(path + root.val);
return;
}
if(root.left != null) robot(root.left, path + root.val + "->", ans);
if(root.right != null) robot(root.right, path + root.val + "->", ans);
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<String>();
if(root != null) {
robot(root, "", ans);
}
return ans;
}
}
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.
public class Solution {
public TreeNode robot(int[] nums, int start, int end) {
if(start > end) return null;
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
// 已經(jīng)是排序數(shù)組，所以只要找中點即可
root.left = robot(nums, start, mid - 1);
root.right = robot(nums, mid + 1, end);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
// 二分驼唱，才會「高度平衡」
if(nums.length == 0) return null;
return robot(nums, 0, nums.length - 1);
}
}
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
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null) return;
if(root.left != null) {
root.left.next = root.right;
if(root.right != null && root.next != null) {
root.right.next = root.next.left;
}
}
connect(root.left);
connect(root.right);
}
}
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.
思路：相當(dāng)于二分查找藻茂，并不需要挨個遍歷每個節(jié)點。只要從某一節(jié)點開始曙蒸，到左葉子結(jié)點和到右葉子結(jié)點的長度相同捌治，就可以利用性質(zhì)計算出結(jié)點個數(shù)。
public class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = leftHeight(root);
int right = rightHeight(root);
if(left == right) {
return (1 << left) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
public int leftHeight(TreeNode root) {
int depth = 0;
while(root != null) {
root = root.left;
depth++;
}
return depth;
}
public int rightHeight(TreeNode root) {
int depth = 0;
while(root != null) {
root = root.right;
depth++;
}
return depth;
}
}
226. Invert Binary Tree
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
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的性質(zhì)纽窟，前序遍歷的第k個數(shù)肖油，即為第k大的數(shù)。
public class Solution {
private static int number = 0; // 最終結(jié)果
private static int count = 0;
public void robot(TreeNode r) {
if(r.left != null) robot(r.left);
count--;
if(count == 0) {
number = r.val;
return;
}
if(r.right != null) robot(r.right);
}
// 中序遍歷臂港，第k個數(shù)
public int kthSmallest(TreeNode root, int k) {
count = k;
robot(root);
return number;
}
}
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的性質(zhì)森枪，LCA是最后一個值介于兩個節(jié)點之間的節(jié)點。
public class Solution {
public static TreeNode ans = null;
public void robot(TreeNode root, int min, int max) {
if(root == null) return;
robot(root.left, min, max);
if(root.val >= min && root.val <= max) {
ans = root;
return;
}
robot(root.right, min, max);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 中序遍歷审孽，找介于p和q之間的node
if(root == null || p == null || q == null) return null;
int min = Math.min(p.val, q.val);
int max = Math.max(p.val, q.val);
robot(root, min, max);
return ans;
}
}
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的特殊條件∮恿Γ可以分為兩種情況：
- 左右結(jié)點并不互為父子節(jié)點
- 左右結(jié)點互為父子節(jié)點
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left == null ? right : left;
}
}
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.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
robot(root, sb);
return sb.toString();
}
public void robot(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("X").append(",");
} else {
sb.append(root.val + "").append(",");
robot(root.left, sb);
robot(root.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(",")));
return buildTree(nodes);
}
public TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if(val.equals("X")) {
return null;
} else {
TreeNode root = new TreeNode(Integer.valueOf(val));
root.left = buildTree(nodes);
root.right = buildTree(nodes);
return root;
}
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// 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.
思路：實際上是動態(tài)規(guī)劃式散，當(dāng)前結(jié)點分為兩種情況：
- 搶該結(jié)點，那么子節(jié)點就不能搶打颤；
- 不搶該結(jié)點暴拄，那么子節(jié)點可以搶漓滔，也可以不搶。
public class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
return Math.max(robIn(root), robEx(root));
}
public int robIn(TreeNode root) {
if(root == null) return 0;
return robEx(root.left) + robEx(root.right) + root.val;
}
public int robEx(TreeNode root) {
if(root == null) return 0;
return rob(root.left) + rob(root.right);
}
}
