eorder(Node root) {
List<Integer> resultList = new ArrayList<>();
Stack<Node> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
Node cur = stack.pop();
List<Node> list = new ArrayList<>();
list = cur.children;
for(int i = list.size() - 1; i >= 0; i--){
if(list.get(i) != null){
stack.push(list.get(i));
}
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
Node cur = stack.pop();
resultList.add(cur.val);
}
}
return resultList;
}
}
559、N 叉树的最大深度
class Solution {
public int maxDepth(Node root) {
// 非递归
// if(root == null){
// return 0;
// }
// Queue<Node> queue = new LinkedList<>();
// queue.offer(root);
// int size = 1;
// int count = 0;
// while(!queue.isEmpty()){
// count++;
// while(size > 0 ){
// Node temp = queue.poll();
// for(Node k : temp.children){
// if(k != null){
// queue.offer(k);
// }
// }
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归法：后序遍历
return find(root);
}
public int find(Node root){
if(root == null){
return 0;
}
int depth = 0;
if(root.children != null){
for(Node k : root.children){
depth = Math.max(find(k),depth);
}
}
return depth + 1;
}
}
117、填充每个节点的下一个右侧节点指针 II
同上！
104、二叉树的最大深度
![]
(https://img2022.cnblogs.com/blog/3018498/202211/3018498-20221121204402960-1570599807.png)
class Solution {
public int maxDepth(TreeNode root) {
// 非递归
// if(root == null){
// return 0;
// }
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// int count = 0;
// int size = 1;
// while(!queue.isEmpty()){
// count++;
// while(size > 0){
// TreeNode temp = queue.poll();
// if(temp.left != null){queue.offer(temp.left);}
// if(temp.right != null){queue.offer(temp.right);}
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归
return find(root, 0);
}
public int find(TreeNode root, int depth){
if(root == null){
return depth;
}
int left = find(root.left, depth);
int right = find(root.right, depth);
depth = Math.max(left,right) + 1;
return depth;
}
}
111、二叉树的最小深度
class Solution {
public int minDepth(TreeNode root) {
// 非递归，层序遍历
// if(root == null){
// return 0;
// }
// Queue<TreeNode> queue = new LinkedList<>();
// queue.offer(root);
// int size = 1;
// int count = 0;
// while(!queue.isEmpty()){
// count++;
// while(size > 0){
// TreeNode temp = queue.poll();
// if(temp.left != null){
// queue.offer(temp.left);
// }
// if(temp.right != null){
// queue.offer(temp.right);
// }
// if(temp.left == null && temp.right == null){
// return count;
// }
// size--;
// }
// size = queue.size();
// }
// return count;
// 递归
if(root == null){
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if(root.left == null && root.right != null){
return 1 + right;
}
if(root.right == null && root.left != null){
return 1 + left;
}
return Math.min(left, right) + 1;
}
}
222、完全二叉树的节点个数
class Solution {
public int count = 0;
public int countNodes(TreeNode root) {
if(root == null){
return count;
}
count++;
countNodes(root.left);
countNodes(root.right);
return count;
}
}
110、平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return check(root) != -1;
}
public int check(TreeNode root){
if(root == null){