102. 二叉树的层序遍历
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
getListByLevel(root, 0);
return list;
}
private void getListByLevel(TreeNode root, int level) {
if (root == null) return;
if (list.size() == level) {
list.add(new ArrayList<>()); // 有一个元素了
}
list.get(level).add(root.val);
getListByLevel(root.left, level + 1);
getListByLevel(root.right, level + 1);
}
层序遍历，不可避免地想到遍历时与深度的关联性
当遍历第一层时，deep = 0，这时候list.size()也等于0,所以需要加入列表。
- 二叉树的层序遍历 II
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) return list;
getListByNode(root, 0);
// reverseList();
Collections.reverse(list);
return list;
}
private void reverseList() {
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < list.size(); i++) {
stack.push(list.get(i));
}
List<List<Integer>> demoList = new ArrayList<>(stack.size());
while (!stack.isEmpty()) {
demoList.add(stack.pop());
}
list = demoList;
}
private void getListByNode(TreeNode root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
getListByNode(root.left, deep+1);
getListByNode(root.right, deep+1);
}
和层次遍历I区别不大
- 二叉树的右视图
List<Integer> list = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return list;
}
getListByRoot(root, 0);
return list;
}
private void getListByRoot(TreeNode root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(root.val);
}
getListByRoot(root.right, deep + 1);
getListByRoot(root.left, deep + 1);
}
当size和deep相等的时候才放入，意味着，每一层只放入一个元素。
由于是先放入的右子树，那么默认会先存放右子树的元素，然后才考虑左子树
637.二叉树的层平均值
List<List<Integer>> list = new ArrayList<>();
public List<Double> averageOfLevels(TreeNode root) {
List<Double> doubles = new ArrayList<>();
if (root == null) {
return doubles;
}
getListByDeep(root, 0);
averageList(doubles);
return doubles;
}
private void averageList(List<Double> doubles) {
for (int i = 0; i < list.size(); i++) {
List<Integer> list1 = list.get(i);
double sum = 0;
for (int j = 0; j < list1.size(); j++) {
sum +=list1.get(j);
}
doubles.add(sum / list1.size());
}
}
private void getListByDeep(TreeNode root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
getListByDeep(root.left, deep+1);
getListByDeep(root.right, deep+1);
}
429. N 叉树的层序遍历
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if (root== null) {
return list;
}
getListByLevel(root, 0);
return list;
}
private void getListByLevel(Node root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
List<Node> children = root.children;
if (children == null) {
return;
}
for(Node child : children) {
getListByLevel(child, deep + 1);
}
}
不要被多叉树迷惑了，多叉树也只是一个遍历罢了
515. 在每个树行中找最大值
List<List<Integer>> list = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
getListByLevel(root, 0);
return getMaxByList();
}
private List<Integer> getMaxByList() {
List<Integer> maxList = new ArrayList<>(list.size());
for (List<Integer> list1 : list) {
Integer max = Collections.max(list1);
maxList.add(max);
}
return maxList;
}
private void getListByLevel(TreeNode root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(new ArrayList<>());
}
list.get(deep).add(root.val);
getListByLevel(root.left, deep + 1);
getListByLevel(root.right, deep + 1);
}
116. 填充每个节点的下一个右侧节点指针 117. 填充每个节点的下一个右侧节点指针 II
public class Demo01 {
List<Stack<Node>> list = new ArrayList<>();
public Node connect(Node root) {
if (root == null) {
return root;
}
Node cur = root;
connectByDepth(cur, 0);
return root;
}
private void connectByDepth(Node root, int deep) {
if (root == null) {
return;
}
if (list.size() == deep) {
list.add(new Stack<>());
// list.get(deep).push(root);
} else {
Node pop = list.get(deep).pop();
root.next = pop;
}
list.get(deep).push(root);
connectByDepth(root.right, deep + 1);
connectByDepth(root.left, deep + 1);
}
}
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;
}
}
先将右子树放入栈中，这样每一次弹出的都是右边的节点，让当前节点指向右节点即可。然后再放入当前节点。
104. 二叉树的最大深度
private int maxDeep = 0;
public int maxDepth(TreeNode root) {
if (root == null) {
return maxDeep;
}
getDeepByTreeNode(root, 0);
return maxDeep;
}
private void getDeepByTreeNode(TreeNode root, int deep) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) { // 根节点
maxDeep = Math.max(deep + 1, maxDeep);
}
getDeepByTreeNode(root.left, deep + 1);
getDeepByTreeNode(root.right, deep + 1);
}
111. 二叉树的最小深度
private int minDeep = Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
getMinDeep(root, 0);
return minDeep;
}
private void getMinDeep(TreeNode root, int deep) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
minDeep = Math.min(minDeep, deep + 1);
}
getMinDeep(root.left, deep + 1);
getMinDeep(root.right, deep + 1);
}
226. 翻转二叉树
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode right = invertTree(root.left);
TreeNode left = invertTree(root.right);
root.left = left;
root.right = right;
return root;
}
