• Leecode DAY16: 二叉树的最大深度 and 二叉树的最小深度 and 完全二叉树的节点个数

    104.二叉树的最大深度(递归)

    终止条件：root == None

    max（左，右子树最大深度） + 1

    1. class Solution:
    2.     def maxDepth(self, root: Optional[TreeNode]) -> int:
    3.         if not root: 
    4.             return 0
    5.         leftDepth = self.maxDepth(root.left)
    6.         rightDepth = self.maxDepth(root.right)
    7.         Depth = 1 + max(leftDepth, rightDepth)
    8.         return Depth

    111.二叉树的最小深度(递归)

    如果左右子树都存在  那么   minDepth = min（左，右子树最小深度）+ 1

    如果只存在左/右子树 那么 minDepth = min（左 / 右子树最小深度）+ 1

    如果左右子树 都不存在  minDepth = 1

    1. class Solution:
    2.     def minDepth(self, root: Optional[TreeNode]) -> int:
    3.         if not root:
    4.             return 0
    5.         if root.right and root.left:
    6.             leftDepth = self.minDepth(root.left)
    7.             rightDepth = self.minDepth(root.right)
    8.             Depth = 1 + min(leftDepth, rightDepth)
    9.         elif root.right and not root.left:
    10.             Depth = 1 + self.minDepth(root.right)
    11.         elif not root.right and root.left:
    12.             Depth = 1 + self.minDepth(root.left)
    13.         else:
    14.             Depth = 1
    15.         return Depth

    222.完全二叉树的节点个数（递归)

    1. class Solution:
    2.     def countNodes(self, root: Optional[TreeNode]) -> int:
    3.         if not root:
    4.             return 0
    5.         rightN = self.countNodes(root.right)
    6.         leftN = self.countNodes(root.left)
    7.         return rightN + leftN + 1

    递归的思想 节点数 = 左子树节点数 + 右子树节点数 + 1

     

  • 相关阅读:
    回流重绘零负担，网页加载快如闪电
    JavaScript 基础第三天笔记
    Hadoop -- NN和2NN的工作机制
    自动化测试的统筹规划
    docker入门到精通一文搞定
    面试官：同学，冒泡太简单了，要不手写一个【快速排序】吧...
    8软件工程环境
    ArcGis Pro Geometry 方法小记
    Redis基础
    模型压缩-剪枝算法详解
  • 原文地址：https://blog.csdn.net/qq_44189622/article/details/128128197