代码随想录二刷day16

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一、力扣104. 二叉树的最大深度

递归

/*** 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 l = maxDepth(root.left);int r = maxDepth(root.right);return l > r ? l + 1 : r + 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) {Deque<TreeNode> deq = new LinkedList<>();if(root == null)return 0;deq.offerLast(root);int high = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();if(p.left!= null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}high ++;}return high;}
}

二、力扣559. N 叉树的最大深度

迭代

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public int maxDepth(Node root) {Deque<Node> deq = new LinkedList<>();if(root == null)return 0;deq.offerLast(root);int high = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){Node p = deq.pollFirst();List<Node> li = p.children;for(Node n : li){if(n != null){deq.offerLast(n);}}}high ++;}return high;}
}

递归

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public int maxDepth(Node root) {if(root == null)return 0;int[] arr = new int[root.children.size()];int max = 0;for(int i = 0; i < arr.length; i ++){arr[i] = maxDepth(root.children.get(i));max = max > arr[i] ? max : arr[i];}return max + 1;}
}

三、力扣111. 二叉树的最小深度

迭代

/*** 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) {Deque<TreeNode> deq = new LinkedList<>();if(root == null)return 0;deq.offerLast(root);int depth = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i <len ; i ++){TreeNode p = deq.pollFirst();if(p.left == null && p.right == null){return depth + 1;}if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}depth ++;}return depth;}
}

递归

class Solution {/*** 递归法，相比求MaxDepth要复杂点* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量*/public int minDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);if (root.left == null) {return rightDepth + 1;}if (root.right == null) {return leftDepth + 1;}// 左右结点都不为nullreturn Math.min(leftDepth, rightDepth) + 1;}
}

三、力扣力扣222. 完全二叉树的节点个数

迭代

/*** 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) {Deque<TreeNode> deq = new LinkedList<>();if(root == null)return 0;deq.offerLast(root);int count = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len ; i ++){TreeNode p = deq.pollFirst();count ++;if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}}return count;}
}

递归

/*** 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 l = countNodes(root.left);int r = countNodes(root.right);return l + r + 1;}
}