二叉树的层次遍历2

在最基础的层次遍历上反转即可

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List> levelOrderBottom(TreeNode root) {//59-03if(root==null) return new ArrayList>();ArrayList> res = new ArrayList>();Queue q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){int count = q.size();List row = new ArrayList<>();while(count-- >0){TreeNode node = q.poll();row.add(node.val);if(node.left!=null) q.offer(node.left);if(node.right!=null) q.offer(node.right);}res.add(row);}Collections.reverse(res);//只要加这句就行return res;}
}

199 二叉树的右视图

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List rightSideView(TreeNode root) {//06-13if(root==null) return new ArrayList<>();List res = new ArrayList<>();Queue q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){int count = q.size();while(count-- >0){TreeNode node = q.poll();if(count==0) res.add(node.val);//是0不是1，因为进来的count已经自减了if(node.left!=null) q.offer(node.left);if(node.right!=null) q.offer(node.right);}}return res;}
}

429 N叉树的层次遍历

注意看它定义的数据结构

/*
// Definition for a Node.
class Node {public int val;public List children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List _children) {val = _val;children = _children;}
};
*/class Solution {public List> levelOrder(Node root) {//22-27ArrayList> res = new ArrayList>();if(root==null) return res;Queue q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){int count = q.size();List row = new ArrayList<>();while(count-- >0){Node node = q.poll();row.add(node.val);//List children这么定义的for(int i=0;iif(node.children.get(i)!=null) q.offer(node.children.get(i));}}res.add(row);}return res;}
}

116

看到样例输出以为是list，可是原函数的返回是Node,所以还奇怪了一下，其实只要把root的树的所有next赋值完成，再返回root即可

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/
class Solution {public Node connect(Node root) {//32-41 输出是list?? 返回根Queue q = new LinkedList<>();if(root==null) return root;q.offer(root);while(!q.isEmpty()){int count = q.size();for(int i=0;iNode node = q.poll();if(i==count-1) node.next = null;else node.next = q.peek();//这两句是此题关键//队列中的顶的就是nextif(node.left!=null) q.offer(node.left);if(node.right!=null) q.offer(node.right);}}return root;        }
}

111 二叉树的最小深度

除了之前用的递归写法之外可以用层序遍历
只要判断左右子树都为null 就可以直接返回

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int minDepth(TreeNode root) {//46-49if(root==null) return 0;Queue q = new LinkedList<>();q.offer(root);int sum = 0;while(!q.isEmpty()){int count = q.size();sum++;while(count-- >0){TreeNode node = q.poll();if(node.left==null&&node.right==null) return sum;//求最大深度只要把这行去掉即可if(node.left!=null) q.offer(node.left);if(node.right!=null) q.offer(node.right);}}return sum;}
}

226 翻转二叉树

用前序遍历或者后遍历的写法都可以，本层做的事情就是将左右节点交换

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {//55-57reverse(root);return root;}public void reverse(TreeNode root){//递归结束条件if(root==null) return;//本层做的事TreeNode tmp = root.left;root.left = root.right;root.right = tmp;//前序遍历reverse(root.left);reverse(root.right);}
}

559 n叉树的最大深度

除了用层次遍历外，用递归也很简单，在二叉树的最大深度基础上改一下即可

/*
// Definition for a Node.
class Node {public int val;public List children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List _children) {val = _val;children = _children;}
};
*/class Solution {public int maxDepth(Node root) {//57-00if(root==null) return 0;int max = 0;for(int i=0;imax = Math.max(max,maxDepth(root.children.get(i)));}return max+1;}
}

404 左叶子之和

还是可以用层序遍历，只要判断节点的左节点不为空，且左节点是叶子节点即可

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {//37-40Queue q = new LinkedList<>();q.offer(root);int sum = 0;while(!q.isEmpty()){TreeNode node = q.poll();if(node.left!=null&&node.left.left==null&&node.left.right==null) sum+=node.left.val;if(node.left!=null) q.offer(node.left);if(node.right!=null) q.offer(node.right);}return sum;}
}

257 二叉树到叶子节点的所有路径

写了很久，理解了很久，用队列来，可以记一下这题

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List binaryTreePaths(TreeNode root) {//07-12Queue node = new LinkedList<>();Queue path = new LinkedList<>();List res = new ArrayList<>();node.offer(root);path.offer(Integer.toString(root.val));while(!node.isEmpty()){TreeNode t = node.poll();String s = path.poll();if(t.left==null&&t.right==null) res.add(s);else{if(t.left!=null){node.offer(t.left);path.offer(new StringBuilder(s).append("->").append(Integer.toString(t.left.val)).toString());}if(t.right!=null){node.offer(t.right);path.offer(new StringBuilder(s).append("->").append(Integer.toString(t.right.val)).toString());}}}return res;}
}

112 路径总和（判断有没有即可）

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null) return false;else if(root.val==targetSum&&root.left==null&&root.right==null) return true;else return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}
}

113 路径总和2（返回路径）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {ArrayList path = new ArrayList<>();ArrayList> res = new ArrayList>();public List> pathSum(TreeNode root, int targetSum) {//52if(root==null) return res;dfs(root,targetSum);return res;}public void dfs(TreeNode root, int targetSum){if(root==null) return;path.add(root.val);if(root.val==targetSum&&root.left==null&&root.right==null) res.add(new ArrayList<>(path));dfs(root.left,targetSum-root.val);dfs(root.right,targetSum-root.val);path.remove(path.size()-1);}
}