BFS循环常用比较参数：queue.size()
107. Binary Tree Level Order Traversal II
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
//BFS time(logN+N) space(2N)
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if(root==null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new LinkedList<>();
int size = queue.size();
for(int i=size; i>0; i--){
root = queue.poll();
list.add(root.val);
if(root.left!=null) queue.offer(root.left);
if(root.right!=null) queue.offer(root.right);
}
//头插法 不知道为什么不能用addFirst()
result.add(0, list);
}
return result;
}
}
102. Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> whole = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root==null) return whole;
queue.offer(root);
int num=1;
while(queue.peek()!=null){
List<Integer> list = new LinkedList<>();
int size = queue.size();
for(int i=size; i>0; i--){
root = queue.poll();
list.add(root.val);
if(root.left!=null) queue.offer(root.left);
if(root.right!=null) queue.offer(root.right);
}
whole.add(list);
}
return whole;
}
}
LinkedList 和 ArrayList 的区别：
LinkedList是采用链表实现的，在进行insert和remove动作时在效率上要比ArrayList要好得多!适合用来实现Stack(堆栈)与Queue(队列)。
ArrayList以数组的方式来实现，可以使用索引的方式来快速定位对象的位置，因此对于快速的随机取得对象的需求，使用ArrayList实现执行效率上会比较好。
103. Binary Tree Zigzag Level Order Traversal
class Solution {
//BFS 与之前几题的不同之处是判断depth的奇偶性
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if(root==null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth=0;
//even: from left to right
//odd: from right to left
while(!queue.isEmpty()){
List<Integer> list = new LinkedList();
int size = queue.size();
for(int i=size; i>0; i--){
root=queue.poll();
if(depth%2==0) list.add(root.val);
else list.add(0, root.val);
if(root.left!=null) queue.offer(root.left);
if(root.right!=null) queue.offer(root.right);
}
depth++;
result.add(list);
}
return result;
}
}
上面三道题大同小异，都用了BFS。下面尝试用DFS解第102题。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
level(root, result, 0);
return result;
}
public void level(TreeNode root, List<List<Integer>> result, int height){
if(root==null) return;
//如果相同高度这个node不是第一个的话，不用新建list
if(result.size()<=height) {
List<Integer> list = new LinkedList<>();
result.add(list);
}
result.get(height).add(root.val);
level(root.left, result, height+1);
level(root.right, result, height+1);
}
}
111. Minimum Depth of Binary Tree
DFS recursive
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int height=0;
if(root.left==null && root.right==null) return height+1;
else if(root.left!=null && root.right!=null)
return Math.min(minDepth(root.left), minDepth(root.right))+1;
//一定注意还有以下这种情况：如果左右中只有一个是null，则返回最大深度
else return Math.max(minDepth(root.left), minDepth(root.right))+1;
}
}
BFS iterate：碰到没有子节点的node可以直接返回深度，不用找到最低点。
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int height=0;
while(!queue.isEmpty()){
int size = queue.size();
height++;
for(int i = size; i>0; i--){
TreeNode node = queue.poll();
if(node.left==null && node.right==null) return height;
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
}
return height;
}
}
101. Symmetric Tree
Iterative solution using one queue and many list.
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = size; i>0; i--){
TreeNode node = queue.poll();
if(node!=null) list.add(node.val);
else list.add(-1);
if(node!=null) {
queue.offer(node.left);
queue.offer(node.right);
}
}
for(int i = 0; i<list.size()/2; i++){
if(list.get(i)!=list.get(list.size()-1-i)) return false;
}
}
return true;
}
Improve the solution to use only one queue without lists.
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if(left==null&&right==null) continue;
else if(left==null || right==null) return false;
else if(left.val!=right.val) return false;
else{
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
}
return true;
}
}
DFS recursive solution.
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return helper(root.left, root.right);
}
public boolean helper(TreeNode left, TreeNode right){
if(left==null&&right==null) return true;
else if(left==null || right==null) return false;
else return (right.val==left.val) && helper(left.left, right.right)
&& helper(left.right, right.left);
}
}
513. Find Bottom Left Tree Value
思路：
- 先dfs找到深度，再bfs找最深一层的第一个。
改进：2. 直接bfs循环的时候记录每一层第一个的值，最后返回。
改进：3. bfs从右到左循环，返回整个循环的最后一个node的值。
class Solution {
//BFS: 找到最后一层最左边的一个 time: O(n) space: O(n)
public int findBottomLeftValue(TreeNode root) {
int result=root.val;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
root = queue.poll();
if(root.right!=null) queue.offer(root.right);
if(root.left!=null) queue.offer(root.left);
}
return root.val;
}
}
DFS方法待补充
515. Find Largest Value in Each Tree Row
BFS solution (pass!)
//BFS
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new LinkedList<>();
if(root==null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int max = Integer.MIN_VALUE;
for(int i=queue.size(); i>0; i--){
root = queue.poll();
if(root.val>max) max=root.val;
if(root.left!=null) queue.offer(root.left);
if(root.right!=null) queue.offer(root.right);
}
list.add(max);
}
return list;
}
}
DFS
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new ArrayList<>();
return helper(root, 0, list);
}
public List<Integer> helper(TreeNode root, int level, List<Integer> list){
if(root==null) return list;
if(list.size()<=level) list.add(root.val);
else if(root.val > list.get(level)) list.set(level, root.val);
helper(root.left, level+1, list);
helper(root.right, level+1, list);
return list;
}
}
623. Add One Row to Tree
dfs
class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
if(root==null) return null;
if(d==1){
TreeNode left = new TreeNode(v);
left.left=root;
return left;
}
if(d==2){
TreeNode left = new TreeNode(v);
left.left = root.left;
root.left = left;
TreeNode right = new TreeNode(v);
right.right = root.right;
root.right = right;
return root;
}
addOneRow(root.left, v, d-1);
addOneRow(root.right, v, d-1);
return root;
}
}
671. Second Minimum Node In a Binary Tree
DFS
// the tree is non empty
// every node has none or two sub-node
class Solution {
public int findSecondMinimumValue(TreeNode root) {
return dfs(root, root.val);
}
public int dfs(TreeNode root, int result){
if(root==null) return -1; //如果没有找到，返回-1
//如果子节点大于最小值，直接返回子节点的值，不用继续递归
//因为其子节点的值一定大于等于现在的值
if(root.val>result) return root.val;
int left = dfs(root.left, result);
int right = dfs(root.right, result);
if(left==-1) return right;
else if(right==-1) return left;
//如果左右结果都不是-1， 说明都比最小值大，返回其中较小的
else return Math.min(left, right);
}
}
BFS
class Solution {
public int findSecondMinimumValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int smallest = root.val;
int result = Integer.MAX_VALUE;
queue.offer(root);
while(!queue.isEmpty()){
root = queue.poll();
//如果这个node和最小值相等，则把它的子节点加入queue
if(root.val==smallest && root.left!=null){
queue.offer(root.left);
queue.offer(root.right);
}
//如果当前node大于最小值，不用加入其子节点。
if(root.val>smallest && root.val<result) result=root.val;
}
return result==Integer.MAX_VALUE ? -1 : result;
}
}
116. Populating Next Right Pointers in Each Node
dfs recursive solution
//all leaves are at the same level, and every parent has two children
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
if(root.left!=null) {
root.left.next=root.right;
if(root.next!=null) root.right.next=root.next.left;
}
connect(root.left);
connect(root.right);
}
}
bfs without extra space
public class Solution {
public void connect(TreeLinkNode root) {
while(root!=null){
TreeLinkNode leftMost = root;
while(root!=null && root.left!=null){
root.left.next=root.right;
if(root.next!=null) root.right.next=root.next.left;
root=root.next;
}
root=leftMost.left;
}
}
}
117. Populating Next Right Pointers in Each Node II
iterative 太复杂了
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode leftMost = root;
//every level
while(root!=null){
leftMost=root;
//every connect in this level
while(root!=null){
TreeLinkNode cur = root;
if(root.right!=null) {
if(root.left!=null) root.left.next=root.right;
cur=root.right;
}
else if(root.left!=null) cur=root.left;
else{
root=root.next;
continue;
}
TreeLinkNode next = root.next;
if(next!=null){
while(next!=null && next.left==null && next.right==null) next=next.next;
if(next==null) break;
if(next.left!=null) cur.next=next.left;
else if(next.right!=null) cur.next=next.right;
}
root=next;
}
while(leftMost!=null && leftMost.left==null && leftMost.right==null) leftMost=leftMost.next;
if(leftMost==null) return;
if(leftMost.left!=null) root=leftMost.left;
else root=leftMost.right;
}
}
}
用dummy start 重新做
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode pre = dummy;
//every level
while(root!=null){
if(root.left!=null){
pre.next=root.left;
pre=pre.next;
}
if(root.right!=null){
pre.next=root.right;
pre=pre.next;
}
root=root.next;
//如果遍历到这个level最后一个node，pre.next是下一个level的开头
if(root==null){
pre=dummy;
root=dummy.next;
//一定要加这一句，否则死循环
dummy.next=null;
}
}
}
}
235. Lowest Common Ancestor of a Binary Search Tree
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return root;
//node的值比pq都小，说明目标节点在它右边
if(root.val>p.val && root.val>q.val)
return lowestCommonAncestor(root.left, p, q);
//node的值比pq都大，说明目标节点在它左边
else if (root.val<p.val && root.val<q.val)
return lowestCommonAncestor(root.right, p, q);
//node的值在pq中间，直接返回；如果等于q或者等于p，直接返回
else return root;
}
}
236. Lowest Common Ancestor of a Binary Tree
dfs recursive
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);
//如果两边都是null：说明两边为空，返回根节点
//如果左边找到了，右边是空，返回左边；反之返回右边
//如果两边都找到了，说明根节点左边也有右边也有，返回根节点
return left==null ? right : (right==null ? left : root);
}
}
617. Merge Two Binary Trees
//DFS
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
//当其中一个为空，此节点以下所有节点都变成另一个为根节点的子树
if(t1==null) return t2;
if(t2==null) return t1;
//当两个node都不为空时，t1的值变为两个值之和
t1.val+=t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
654. Maximum Binary Tree
思路：遍历，找到最大值和最大值的index，再在最大值的左边和右边分别找最大值。
//DFS time: O(n^2) space: O(n) （pass）
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return recursive(nums, 0, nums.length-1);
}
public TreeNode recursive(int[] nums, int start, int end){
if(start>end) return null;
int max = nums[start];
int index = start;
for(int i=start; i<=end; i++){
if(nums[i]>max) {
max = nums[i];
index = i;
}
}
TreeNode root = new TreeNode(max);
root.left=recursive(nums, start, index-1);
root.right=recursive(nums, index+1, end);
return root;
}
}
优化：
//待补充
网友评论