代码随想录算法训练营第十六天|104. 二叉树的最大深度、559. N 叉树的最大深度、111. 二叉树的最小深度、222. 完全二叉树的节点个数-526互联

【参考链接】

104. 二叉树的最大深度

【注意】

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）。

2.根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

3.通过后序把结果传递给父节点，父节点再加1。

4.真正求深度是用前序。

5.最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def maxDepth(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: int
12         """
13         #1.递归法
14         return self.getdepth(root)
15     
16     def getdepth(self,node):
17         if not node:
18             return 0
19         leftheight = self.getdepth(node.left)
20         rightheight = self.getdepth(node.right)
21         height = 1 + max(leftheight,rightheight)
22 
23         return height

559. N 叉树的最大深度

【代码】

 1 """
 2 # Definition for a Node.
 3 class Node(object):
 4     def __init__(self, val=None, children=None):
 5         self.val = val
 6         self.children = children
 7 """
 8 
 9 class Solution(object):
10     def maxDepth(self, root):
11         """
12         :type root: Node
13         :rtype: int
14         """
15         #1.迭代法
16         if not root:
17             return 0
18         
19         max_depth = 1
20 
21         for child in root.children:
22             max_depth = max(max_depth, self.maxDepth(child)+1)
23         return max_depth

111. 二叉树的最小深度

【注意】

1.最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

2.前序求的是深度，后序求的是高度。

3.使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也同样是最小深度。

【代码】

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution(object):
 8     def minDepth(self, root):
 9         """
10         :type root: TreeNode
11         :rtype: int
12         """
13         #1.递归法
14         if not root:
15             return 0
16         if not root.left and not root.right:
17             return 1
18         
19         left_depth = float('inf')
20         right_depth = float('inf')
21 
22         if root.left:
23             left_depth = self.minDepth(root.left)
24         if root.right:
25             right_depth = self.minDepth(root.right)
26         
27         return 1 + min(left_depth, right_depth)