• 欢迎光临~

代码随想录训练营|Day 16|104,111,222

开发技术 开发技术 2022-10-05 次浏览

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:

代码随想录训练营|Day 16|104,111,222

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:

代码随想录训练营|Day 16|104,111,222

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:

代码随想录训练营|Day 16|104,111,222

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/

程序员灯塔
转载请注明原文链接:代码随想录训练营|Day 16|104,111,222
喜欢 (0)