104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 100 <= Node.val <= 100
先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
Recursion
class solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
Iteration
class solution {
/**
* 迭代法，使用层序遍历
*/
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return depth;
}
}
Time Complexity：O(n)
Space Complexity：O(log n)
For Future References
题目链接：https://leetcode.com/problems/maximum-depth-of-binary-tree/
文章讲解：https://programmercarl.com/0104.二叉树的最大深度.html#递归法
视频讲解：https://www.bilibili.com/video/BV1Gd4y1V75u/
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Constraints:
- The number of nodes in the tree is in the range
[0, 105]. 1000 <= Node.val <= 1000
单层递归的逻辑:
- 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
- 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
- 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
Recursion
class Solution {
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;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}
Iteration
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode poll = deque.poll();
if (poll.left == null && poll.right == null) {
// 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
return depth;
}
if (poll.left != null) {
deque.offer(poll.left);
}
if (poll.right != null) {
deque.offer(poll.right);
}
}
}
return depth;
}
}
Time Complexity：O(n)
Space Complexity：O(log n)
For Future References
题目链接：https://leetcode.com/problems/minimum-depth-of-binary-tree/
文章讲解：https://programmercarl.com/0111.二叉树的最小深度.html#递归法
视频讲解：https://www.bilibili.com/video/BV1QD4y1B7e2/
222. Count Complete Tree Nodes
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6
Example 2:
Input: root = []
Output: 0
Example 3:
Input: root = [1]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
情况一：就是满二叉树,可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
情况二：最后一层叶子节点没有满。分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {// 左子树是满二叉树
// 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
return (1 << leftDepth) + countNodes(root.right);
} else {// 右子树是满二叉树
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
}
Time Complexity：O(log n × log n)
Space Complexity：O(log n)
For Future References
题目链接：https://leetcode.com/problems/count-complete-tree-nodes/
文章讲解：https://programmercarl.com/0222.完全二叉树的节点个数.html#普通二叉树
视频讲解：https://www.bilibili.com/video/BV1eW4y1B7pD/
标签：deque,return,16,int,随想录,depth,null,root,222 From： https://www.cnblogs.com/bluesociety/p/16756924.html