文章目录
- 144.二叉树的前序遍历
- 145.二叉树的后序遍历
- 94.二叉树的中序遍历
- 102.二叉树的层序遍历
- 107.二叉树的层次遍历倒序
- 199.二叉树的右视图
- 637.二叉树的层平均值
- 429.N叉树的层序遍历
- 515.在每个树行中找最大值
- 116.填充每个节点的下一个右侧节点指针
- 104.二叉树的最大深度
- 111.二叉树的最小深度
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();traversal(res,root);return res;}public void traversal(List<Integer> res ,TreeNode root){if(root == null){return;}res.add(root.val);traversal(res,root.left);traversal(res,root.right);}
}
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();traversal(res,root);return res;}public void traversal(List<Integer> list, TreeNode root){if(root == null){return;}traversal(list,root.left);traversal(list,root.right);list.add(root.val);}
}
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();traversal(res,root);return res;} public void traversal(List<Integer> list,TreeNode root){if(root == null){return;}traversal(list,root.left);list.add(root.val);traversal(list,root.right);}
}
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();traversal(res,root,0);return res;}public void traversal(List<List<Integer>> list,TreeNode root, int deep){if(root == null){return;}if(list.size() < deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);traversal(list,root.left,deep+1);traversal(list,root.right,deep+1);}
}
class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();traversal(res,root,0);Collections.reverse(res);return res;}public void traversal(List<List<Integer>> list,TreeNode root,int deep){if(root == null){return;}if(list.size() < deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);traversal(list,root.left,deep+1);traversal(list,root.right,deep+1);}
}
class Solution {public List<Integer> rightSideView(TreeNode root) {List<List<Integer>> res = new ArrayList<>();traversal(res,root,0);List<Integer> result = new ArrayList<>();for(List<Integer> list:res){result.add(list.getLast());}return result;}public void traversal(List<List<Integer>> list,TreeNode root,int deep){if(root == null){return;}while(list.size() <deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);traversal(list,root.left,deep+1);traversal(list,root.right,deep+1);}
}
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<List<Integer>> rest = new ArrayList<>();List<Double> res = new ArrayList<>();traversal(rest,root,0);for(List<Integer> l :rest){res.add(l.stream().mapToInt(Integer::intValue).average().orElse(0));}return res;}public void traversal(List<List<Integer>> list,TreeNode root,int deep){if(root == null){return;}if(list.size() < deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);traversal(list,root.left,deep+1);traversal(list,root.right,deep+1);}
}
class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> res = new ArrayList<>();traversal(res,root,0);return res;}public void traversal(List<List<Integer>> list,Node root,int deep){if(root == null){return;}if(list.size() < deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);for(Node node : root.children){traversal(list,node,deep+1);}}
}
class Solution {public List<Integer> largestValues(TreeNode root) {List<List<Integer>> res = new ArrayList<>();traversal(res,root,0);List<Integer> result = new ArrayList<>();for(List<Integer> l : res){result.add(l.stream().max(Integer::compare).orElse(0));}return result;}public void traversal(List<List<Integer>> list, TreeNode root, int deep){if(root == null){return;}if(list.size() < deep+1){list.add(new ArrayList<>());}list.get(deep).add(root.val);traversal(list,root.left,deep+1);traversal(list,root.right,deep+1);}
}
class Solution {public Node connect(Node root) {if(root == null){return root;}Queue<Node> nodeq = new LinkedList<>();nodeq.add(root);while(!nodeq.isEmpty()){int size = nodeq.size();for(int i = 0; i < size; i++){Node node = nodeq.poll();if(i < size - 1){node.next = nodeq.peek();}if(node.left != null){nodeq.add(node.left);}if(node.right != null){nodeq.add(node.right);}}}return root;}}
class Solution {public int maxDepth(TreeNode root) {if(root == null){return 0;}int leftH = maxDepth(root.left);int rightH = maxDepth(root.right);return Math.max(leftH,rightH) + 1;}
}
class Solution {public int minDepth(TreeNode root) {if(root == null){return 0;}int leftH = minDepth(root.left);int rightH = minDepth(root.right);if(leftH == 0 || rightH == 0){return Math.max(leftH,rightH) + 1;}return Math.min(leftH,rightH)+ 1;}
}
