本文主要是介绍代码随想录训练营第三十五期|第天16|二叉树part03|104.二叉树的最大深度 ● 111.二叉树的最小深度● 222.完全二叉树的节点个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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;}
}
这篇关于代码随想录训练营第三十五期|第天16|二叉树part03|104.二叉树的最大深度 ● 111.二叉树的最小深度● 222.完全二叉树的节点个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!