共计 8680 个字符，预计需要花费 22 分钟才能阅读完成。
这两天在做 tree 的题目（easy），基本上每道都实现了 **recursive** 和 **iterative** 两种解法，简单整理一下。
感想：
能用 BFS+queue 解决的基本都可以用 DFS+stack 解决，尤其是用 preorder，因为它有一种写法和层序遍历十分相近。
遍历两棵树的问题（有时是同一棵树的左右子树）最重要的就是要解决同步的问题。
100. Same Tree
Given two binary trees, write a function to check if they are the same or not.Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Recursive Solution
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null || p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
BFS Solution：用一个 queue
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while(!queue.isEmpty()){
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if(node1 == null && node2 == null) continue;
if(node1 == null || node2 == null || node1.val != node2.val) return false;
queue.offer(node1.left);
queue.offer(node2.left);
queue.offer(node1.right);
queue.offer(node2.right);
}
return true;
}
}
DFS Solution: 用两个 stack 和 BFS 同样的思路来实现（代码是 preorder 的，但是顺序不重要，核心是遍历）
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(p);
stack2.push(q);
while (!stack1.isEmpty() && !stack2.isEmpty()) {
TreeNode node1 = stack1.pop();
TreeNode node2 = stack2.pop();
if (node1 == null && node2 == null) continue;
if (node1 == null || node2 == null) return false;
if (node1.val != node2.val) return false;
stack1.push(node1.right);
stack2.push(node2.right);
stack1.push(node1.left);
stack2.push(node2.left);
}
return true;
}
}
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
分析：这题是第 100 题的变体，可以看成判断一棵树的左右子树是否是镜像对称，且如果 A,B 两棵树是镜像堆成的，那么 A 树的左子树和 B 树的右子树镜像对称，A 树的右子树和 B 树的左子树镜像堆成，且根节点相等。
Recursive Solution
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetricHelper(root.left, root.right);
}
public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
if (left.val == right.val && isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left)) return true;
return false;
}
}
BFS+queue Solution
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null || root.left == null && root.right == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if (node1 == null && node2 == null) continue;
if (node1 == null || node2 == null) return false;
if (node1.val != node2.val) return false;
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}
DFS+stack solution
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root.left);
stack2.push(root.right);
while (!stack1.isEmpty() && !stack2.isEmpty()) {
TreeNode node1 = stack1.pop();
TreeNode node2 = stack2.pop();
if (node1 == null && node2 == null) continue;
if (node1== null || node2 == null) return false;
if (node1.val != node2.val) return false;
stack1.push(node1.right);
stack2.push(node2.left);
stack1.push(node1.left);
stack2.push(node2.right);
}
return true;
}
}
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).
Recursive Solution（真的想不出）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
// if (root == null) return wrapList;
levelOrderMaker(wrapList, root, 0);
return wrapList;
}
public void levelOrderMaker(List<List<Integer>> wrapList, TreeNode root, int level) {
if (root == null) return;
if (level == wrapList.size())
wrapList.add(new LinkedList<Integer>());
wrapList.get(level).add(root.val);
levelOrderMaker(wrapList, root.left, level + 1);
levelOrderMaker(wrapList, root.right, level + 1);
}
}
BFS Solution
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> wrapList= new LinkedList<>();
if (root == null) return wrapList;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> subList = new LinkedList<>();
int size = queue.size();
for (int i = 0; i < size; i ++) {
TreeNode node = queue.poll();
subList.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
wrapList.add(subList);
}
return wrapList;
}
}
BFS 的这种写法和常规写法的不同之处在于，每次循环都遍历了这一层的所有节点。因此这种解法也可以用来求 tree 的最大深度和最小深度，在此就不整理了。另外 107 题和 102 几乎相同，只要将 BFS Solution 中 wrapList.add(subList) 改为 wraplist.add(0, subList) 即可。Recursive Solution 中将
if (level == wrapList.size())
wrapList.add(new LinkedList<Integer>());
wrapList.get(level).add(root.val);
改为
if (level == wrapList.size())
wrapList.add(0, new LinkedList<Integer>());
wrapList.get(wrapList.size()-level-1).add(root.val);
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.
mutipass: 非常直观的解法，从平衡树的定义入手：左右子树均为平衡树且子树的高度差不超过 1
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (Math.abs(height(root.left) – height(root.right)) <= 1 &&
isBalanced(root.left) && isBalanced(root.right)) return true;
return false;
}
private int height(TreeNode root) {
if (root == null) return 0;
return Math.max(height(root.left), height(root.right)) + 1;
}
}
但是这种解法会存在大量的重复计算，于是就有了第二种解法，时间复杂度为 O(n)。onepass（真的想不出）
class Solution {
public boolean isBalanced(TreeNode root) {
return balanceHeight(root) != -1;
}
private int balanceHeight(TreeNode root) {
if (root == null) return 0;
int lHeight = balanceHeight(root.left);
if (lHeight == -1) return -1;
int rHeight = balanceHeight(root.right);
if (rHeight == -1) return -1;
if (Math.abs(lHeight-rHeight) > 1) return -1;
return Math.max(lHeight, rHeight) + 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.
分析：hasPathSum(root.left, sum-root.val) 或 hasPathSum(root.right, sum-root.val) 成立即可
Recursive Solution（意外得好写）：
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
if (hasPathSum(root.left, sum-root.val) == true ||hasPathSum(root.right, sum-root.val) == true) return true;
return false;
}
}
BFS+queue：（每个叶子节点到根节点的路径是唯一的，所以可以在遍历过程中将每个节点到根的路径上的节点和存起来，当然用 stack 也是完全可以的）
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
Queue<TreeNode> Q1 = new LinkedList<TreeNode>();
Queue<Integer> Q2 = new LinkedList<Integer>();
Q1.offer(root);
Q2.offer(root.val);
while(!Q1.isEmpty()) {
int size = Q1.size();
for (int i = 0; i < size; i ++) {
TreeNode node = Q1.poll();
int val = Q2.poll();
if (val == sum && node.left == null && node.right == null) return true;
if (node.left != null) {
Q1.offer(node.left);
Q2.offer(val + node.left.val);
}
if (node.right != null) {
Q1.offer(node.right);
Q2.offer(val + node.right.val);
}
}
}
return false;
}
}
226. Invert Binary Tree
Invert a binary tree.
recursive solution：
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode tmp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(tmp);
return root;
}
}
BFS Solution（在遍历过程中交换左右节点，用 stack+preorder 也是一样的道理，不放代码了）
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}
}
617. Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree
Recursive solution
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}
BFS Solution（很好地解决了同步遍历两棵树的问题）
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
Queue<TreeNode> queue1 = new LinkedList<>();
Queue<TreeNode> queue2 = new LinkedList<>();
queue1.offer(t1);
queue2.offer(t2);
while (!queue1.isEmpty()) {
TreeNode node1 = queue1.poll();
TreeNode node2 = queue2.poll();
node1.val += node2.val;
if (node1.left == null && node2.left != null)
node1.left = node2.left;
else if (node1.left != null && node2.left != null) {
queue1.add(node1.left);
queue2.add(node2.left);
}
if (node1.right == null && node2.right != null)
node1.right = node2.right;
else if (node1.right != null && node2.right != null) {
queue1.add(node1.right);
queue2.add(node2.right);
}
}
return t1;
}
}