D16|二叉树的深度+完全二叉树节点数量

66 阅读 0 评论 44 点赞

我是靠谱客的博主高大白云，最近开发中收集的这篇文章主要介绍D16|二叉树的深度+完全二叉树节点数量，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

104. 二叉树的最大深度

1.题目
104. 二叉树的最大深度
2.复习前
用递归的方法，想好单层逻辑，且计算深度和数量的可以考虑有返回值的情况，这样会写的简便很多，轻松解决~

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

3.文章讲解
1）二叉树的最大深度和高度，height value == max_depth value
2）深度用前序遍历，高度用后序遍历，这里求高度比较简便

class solution {
public:
    int result;
    void getdepth(treenode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }
    int maxdepth(treenode* root) {
        result = 0;
        if (root == 0) return result;
        getdepth(root, 1);
        return result;
    }
};

class solution:
    def maxdepth(self, root: treenode) -> int:
        return self.getdepth(root)
        
    def getdepth(self, node):
        if not node:
            return 0
        leftdepth = self.getdepth(node.left) #左
        rightdepth = self.getdepth(node.right) #右
        depth = 1 + max(leftdepth, rightdepth) #中
        return depth

111. 二叉树的最小深度

1.题目
111. 二叉树的最小深度
2.文章讲解
1）一定要弄清楚最小深度的定义，根节点到叶子节点的边的数目
2）思路：一是和求最大深度一般，想好单层逻辑，二是定义一个全局变量去记录最小深度
3）注意如果一开始没想好遍历方式，可以在写好单层逻辑去模拟时，想好采取的前中后序遍历

222. 完全二叉树的节点个数

1.题目
222. 完全二叉树的节点个数
2.复习前
感觉用了一种写的很复杂，也用了公式但并没有提升性能的方法

class Solution:
    def __init__(self):
        self.mdepth = 0  
        self.cnt = 0
    
    def countnode(self, root, depth):
        if not root:
            if self.mdepth == 0:
                self.mdepth = depth - 1  # 记录最深深度，从0开始
            return     
        self.countnode(root.left, depth+1)
        if depth == self.mdepth:  # 遵循中序遍历，回到根节点对最后一层+1，防止重复+1
            self.cnt += 1
        self.countnode(root.right, depth+1)
        
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        depth = 0
        self.countnode(root, depth)
        return 2 ** self.mdepth - 1 + self.cnt

3.文章讲解
1）利用完全二叉树的特点，利用公式去求满二叉树的节点数量，而完全二叉树一定可以使得所有的子树都为满二叉树
2）想想这道题的时间复杂度

def countNodes(self, root: Optional[TreeNode]) -> int:
    # 通过判断子树是否为满二叉树来进行求和，如果是则返回，不是则继续遍历
    if not root:
        return 0
    left, right = root.left, root.right
    ldepth, rdepth = 1, 1  # 要注意初始值确定，可以想想1 2 3的情况
    while left:
        ldepth += 1
        left = left.left
    while right:
        rdepth += 1
        right = right.right
    if ldepth == rdepth:
        return 2 ** ldepth - 1
    return self.countNodes(root.left) + self.countNodes(root.right) + 1