• 算法day 16|104，559，111，222

     

    区分：

    深度：根节点到节点的距离：根节点深度为1。最底下的节点（叶子节点）深度为3

    高度：任意一个节点到叶子节点的距离。3那个节点的高度为3，15的高度为1

    求高度：后序遍历。把中间的处理过程返回给父节点

    求深度：前序遍历

    104.二叉树的最大深度 （优先掌握递归）

    1. class Solution(object):
    2.     def maxDepth(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: int
    6.         """
    7.         return self.getDepth(root)
    8.         #求最大深度（根系节点到叶子节点的距离）==求根节点的高度
    9.         #所以这道题用后序遍历
    10.         #终止条件
    11.     def getDepth(self,node):
    12.         if node is None:
    13.             return 0
    14.         #单层逻辑(左右中)
    15.         leftsize = self.getDepth(node.left)
    16.         rightsize = self.getDepth(node.right)
    17.         #因为往上传值
    18.         midsize = max(leftsize,rightsize)+1
    19.         return midsize

    题目链接/文章讲解/视频讲解： 代码随想录

    二刷：未ac

    层序遍历的ac了，递归法没有ac。递归法没有搞清楚怎么来的数字，后面知道时终止条件得到的数字

    1. class Solution:
    2.     def maxDepth(self, root: Optional[TreeNode]) -> int:
    3.         #迭代法,层序遍历
    4.         if root is None:
    5.             return 0
    6.         que = deque()
    7.         que.append(root)
    8.         depth = 0
    9.         
    10.         while que:
    11.             size = len(que)
    12.             while size > 0:
    13.                 node = que.popleft()
    14.                 if node.left:
    15.                     que.append(node.left)
    16.                 if node.right:
    17.                     que.append(node.right)
    18.                 size -= 1
    19.             depth += 1
    20.         return depth
    1. var maxDepth = function(root) {
    2.     //递归法写，后序遍历
    3.     const traversal = function(node){
    4.         if(node === null){
    5.             return 0
    6.         }
    7.         let left = traversal(node.left)
    8.         let right = traversal(node.right)
    9.         let mid = Math.max(left,right)+1
    10.         return mid
    11.     }
    12.     return traversal(root)
    13.     
    14. };

    559.Maximum Depth of N-ary Tree

    1. class Solution(object):
    2.     def maxDepth(self, root):
    3.         """
    4.         :type root: Node
    5.         :rtype: int
    6.         """
    7.         return self.getDepth(root)
    8.         #求最大深度=求高度，使用后序遍历
    9.     def getDepth(self,node):
    10.         #终止条件
    11.         if not node:
    12.             return 0
    13.         #左右中,如果遇上children怎么办？
    14.         #原来是
    15.         # leftsize = self.getDepth(node.left)
    16.         # rightsize = self.getDepth(node.right)
    17.         #因为往上传值
    18.         # midsize = max(leftsize,rightsize)+1
    19.         #children 合并在在一起了，所以使用遍历，但是又不能比较，所以使用depth
    20.         depth = 0
    21.         for i in range(len(node.children)):
    22.             depth = max(self.getDepth(node.children[i]),depth)       
    23.         return depth +1

    二刷：未ac，children不知道怎么写，以后我知道了，使用遍历

    1. class Solution:
    2.     def maxDepth(self, root: 'Node') -> int:
    3.         if root is None:
    4.             return 0
    5.         que = deque()
    6.         que.append(root)
    7.         depth = 0
    8.         while que:
    9.             size = len(que)
    10.             while size > 0:
    11.                 node = que.popleft()
    12.                 if node.children:
    13.                     for i in range(len(node.children)):
    14.                         if node.children[i]:
    15.                             que.append(node.children[i])
    16.                 size -= 1
    17.             depth += 1
    18.         return depth

    111.二叉树的最小深度 （优先掌握递归）

    递归法：

    1. class Solution(object):
    2.     def minDepth(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: int
    6.         """
    7.         return self.getDepth(root)
    8.     def getDepth(self,node):
    9.         if not node:
    10.             return 0
    11.         #单层逻辑，求最小深度==求高度,使用后序遍历，左右中
    12.         leftsize = self.getDepth(node.left)
    13.         rightsize = self.getDepth(node.right)
    14.         #如果碰到左边是空的话，我们不可以直接比较大小取最小值，因为永远是等于0
    15.         if node.left is None and node.right is not None:
    16.             return rightsize + 1
    17.         if node.left is not None and node.right is None:
    18.             return leftsize + 1
    19.         #都不为空
    20.         depth = min(leftsize,rightsize)+1
    21.         return depth

    迭代法：

    1. class Solution(object):
    2.     def minDepth(self, root):
    3.         if root is None:
    4.             return 0
    5.         que = deque()
    6.         depth = 0
    7.         que.append(root)
    8.         while len(que)!=0:
    9.             size = len(que)
    10.             depth += 1
    11.             while size >0:
    12.                 node = que.popleft()
    13.                 if not node.left and not node.right:
    14.                     return depth 
    15.                 if node.left is not None:
    16.                     que.append(node.left)
    17.                 if node.right is not None:
    18.                     que.append(node.right)
    19.                 size -= 1
    20.         return depth

    题目链接/文章讲解/视频讲解：代码随想录

    二刷（未ac）

    三刷

    1. var minDepth = function(root) {
    2.     // 最小深度
    3.     const traversal = function(node){
    4.         if(node === null){
    5.             return 0
    6.         }
    7.         let left = traversal(node.left)
    8.         let right = traversal(node.right)
    9.         // 如果有一边为空
    10.         if(node.left === null && node.right !== null){
    11.             return right+1
    12.         } 
    13.         if(node.right === null && node.left !== null){
    14.             return left+1
    15.         } 
    16.         // 都不为空
    17.         let mid = Math.min(left,right)+1
    18.         return mid
    19.     }
    20.     return traversal(root)
    21. };

    222.完全二叉树的节点个数（优先掌握递归）

    1. class Solution(object):
    2.     def countNodes(self, root):
    3.         if root is None:
    4.             return 0
    5.         que = deque()
    6.         count = 0
    7.         que.append(root)
    8.         while len(que)!=0:
    9.             size = len(que)
    10.             while size >0:
    11.                 count += 1
    12.                 node = que.popleft()
    13.                 if node.left is not None:
    14.                     que.append(node.left)
    15.                 if node.right is not None:
    16.                     que.append(node.right)
    17.                 size -= 1
    18.         return count

    二叉树做法

    1. class Solution(object):
    2.     def countNodes(self, root):
    3.         """
    4.         :type root: TreeNode
    5.         :rtype: int
    6.         """
    7.         
    8.         #满二叉树满足2的深度次方-1
    9.         if root is None:
    10.             return 0
    11.         #使用指针
    12.         left = root.left
    13.         right = root.right
    14.         leftdepth = 0
    15.         rightdepth = 0
    16.         while left is not None:
    17.             left = left.left
    18.             leftdepth += 1
    19.         while right is not None:
    20.             right = right.right
    21.             rightdepth += 1
    22.         if leftdepth == rightdepth:
    23.             #因为depth从0开始的
    24.             return pow(2,leftdepth+1) -1
    25.         #左右中
    26.         return self.countNodes(root.left)+self.countNodes(root.right) +1

    当遇到了非满二叉树的，就继续往下遍历，直到叶子节点（他都指向null，所以是满）

    题目链接/文章讲解/视频讲解：代码随想录

    二刷：

    层序遍历法：（ac）

    1. class Solution:
    2.     def countNodes(self, root: Optional[TreeNode]) -> int:
    3.         #层序遍历
    4.         if root is None:
    5.             return 0
    6.         que = deque()
    7.         que.append(root)
    8.         count = 0
    9.         while que:
    10.             size = len(que)
    11.             while size>0:
    12.                 node = que.popleft()
    13.                 count += 1
    14.                 if node.left:
    15.                     que.append(node.left)
    16.                 if node.right:
    17.                     que.append(node.right)
    18.                 size -= 1
    19.         return count

     递归遍历

    1. class Solution:
    2.     def countNodes(self, root: Optional[TreeNode]) -> int:
    3.         #后序遍历 左右中,中间返回节点个数
    4.         def recursion(node):
    5.             #参数，返回值，终止条件，单层递归逻辑
    6.             if not node:
    7.                 return 0
    8.             left = recursion(node.left)
    9.             right = recursion(node.right)
    10.             mid = left + right + 1
    11.             return mid
    12.         if root is None:
    13.             return 0
    14.         return recursion(root)

    Js:

    1. var countNodes = function(root) {
    2.         // 递归法
    3.         const recursion = function(node){
    4.             // 后序遍历
    5.             if(node===null){
    6.                 return 0;
    7.             }
    8.             let leftsize = recursion(node.left);
    9.             let rightsize = recursion(node.right);
    10.             let midsize = leftsize + rightsize + 1;
    11.             return midsize;
    12.         }
    13.         return recursion(root);
    14. };

    1. var countNodes = function(root) {
    2.     // 层序遍历
    3.     if(root === null){
    4.         return 0;
    5.     }
    6.     let que = []
    7.     que.push(root)
    8.     let count = 0
    9.     while(que.length){
    10.         let size = que.length;
    11.         while(size--){
    12.             let node = que.shift();
    13.             count ++;
    14.             node.left && que.push(node.left);
    15.             node.right && que.push(node.right);
    16.         }
    17.     }
    18.     return count;
    19.     
    20. };

    使用完全二叉树的属性写的 

    1. var countNodes = function(root) {
    2.     if(root === null){
    3.         return 0
    4.     }
    5.     let leftdepth = 1;
    6.     let rightdepth = 1;
    7.     let left = root.left;
    8.     let right = root.right;
    9.     while(left){
    10.         leftdepth ++;
    11.         left = left.left;
    12.         console.log('leftdepth',leftdepth);
    13.     }
    14.     while(right){
    15.         rightdepth ++;
    16.         right = right.right;
    17.         console.log('rightdepth',rightdepth);
    18.     }
    19.     if(leftdepth===rightdepth){
    20.         console.log("euqal")
    21.         return Math.pow(2,leftdepth)-1
    22.     }
    23.     return countNodes(root.left)+countNodes(root.right)+1;
    24.  
    25. };

  • 相关阅读:
    win10环境下搭建QT+opencv
    Mysql创建数据库索引
    dc_shell的change_names命令，信号[]/_
    diff 算法分析
    OnlyOffice documentType类型值
    FreeRadius介绍使用和Java调用
    SpringMVC的架构有什么优势？——表单和数据校验（四）
    macOS 系统 Kafka 快速入门
    怎样做数字化转型?有没有通用的路径和准则?
    python自动化测试selenium核心技术3种等待方式详解
  • 原文地址：https://blog.csdn.net/weixin_42173016/article/details/127794364