徐州做网站xlec,网站开发一级分销,网站app开发,国内网站排名104. 二叉树的最大深度 - 力扣#xff08;LeetCode#xff09;
递归#xff0c;可以前序遍历#xff0c;也可以后序遍历
前序遍历是backtracking
下面是后序遍历的代码#xff1a;
/*** Definition for a binary tree node.* public class TreeNode {* int val;* …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;QueueTreeNode 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;QueueTreeNode 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;}
}
迭代层序遍历每取出一个nodecount 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;QueueTreeNode 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;}
}
