104. 二叉树的最大深度 - 力扣(LeetCode)
递归,可以前序遍历,也可以后序遍历
前序遍历是backtracking
下面是后序遍历的代码:
/**
* 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 maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
层序遍历,到最后一层, 记录遍历了多少层。需要遍历到最后一层
/**
* 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 maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
}
return level;
}
}
111. 二叉树的最小深度 - 力扣(LeetCode)
递归:当一边是空的时候,返回另外一边
/**
* 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) {
if (root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
if (root.left == null && root.right != null) {
return right + 1;
}
if (root.right == null && root.left != null) {
return left + 1;
}
return Math.min(left, right) + 1;
}
}
迭代:
当当前的node的左右孩子都为null的时候,就可以返回level了
/**
* 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) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left == null && cur.right == null) return level;
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
}
return level;
}
}
222. 完全二叉树的节点个数 - 力扣(LeetCode)
递归:
/**
* 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 countNodes(TreeNode root) {
if (root == null) return 0;
int left = countNodes(root.left);
int right = countNodes(root.right);
return left + right + 1;
}
}
迭代:层序遍历,每取出一个node,count + 1
/**
* 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 countNodes(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
count++;
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
}
}
return count;
}
}