【二叉树】实战篇2

前言

本日带大家举行二叉树的实战篇2，学会并相识二叉树属性，无论什么要求深度，还是路径，求和等等，一文带大家弄懂。本文用于纪录自己的学习过程，同时向大家举行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思索过程，如果有错误的地方接待批评指正！

对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

相关本领：首先来看题意哈，我们是要关于root节点轴对称，什么意思呢，就是镜像对称，左边的外面等于右边的外面，左边的里面等于右边的里面，就是这个意思，不符合这个条件的就是非对称了。那这道题怎么解呢？我们用递归的方式来解。还记得之前说过的递归三要素嘛，没啥事，不记得也行，如今带大家回首并实战。

• 确定递归的参数和返回值：很显着看这道题，我们需要做什么，是比较根节点的两个左右子树是否是翻转的，当然具体比较的就是二者的值了，以是我们传入的参数肯定就是两个节点，需要返回的就是二者的比较结果，以是返回值就是True 或者False
  
• 确定递归的制止条件：什么时候制止，这里来看，当符合对称树的情况是不是就一种，两个节点均为空即为制止条件，但是不符合对称树的情况呢？要么左边空右边非空，要么左边非空右边空，要么两者均不为空，但是两者的值不相等，也不属于对称树。
  
• 确定单层递归的逻辑：在确定还没到达递归制止的条件的时候就是单层递归的逻辑了，处理的情况就是二者均不为空且值相等。怎么处理，我们需要比较的是外部（左节点的左孩子，右节点的右孩子)，内部（左节点的右孩子，右节点的左孩子），如果都对称就返回true，有任何一侧不对称返回false
  

故实当代码为：

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def isSymmetric(self, root: Optional[TreeNode]) -> bool:
9.         if not root:
10.             return True
11.         return self.campare(root.left,root.right)
13.     def campare(self,left,right):
14.         if left == None and right != None : return False
15.         elif left != None and right == None : return False
16.         elif left == None and right == None : return True
17.         elif left.val != right.val : return False
19.         outside = self.campare(left.left,right.right)
20.         inside = self.campare(left.right,right.left)
21.         issame = outside and inside
22.         return issame

复制代码

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

相关本领：看到这道题是不是有点熟悉，我们之前讲层序遍历的时候学习过，只不外那是层序遍历的迭代方法求解的，这下我们来看看如何使用递归的方法解这道题。求深度高度这种是不是就是只要左右子树的深度的最大值加1就是当前节点的深度高度了，那么递归下去是不是就可以求出根节点的深度了。同样的我们来看递归三要素：

• 确定递归的参数和返回值：来看这道题，我们需要做什么，是当前节点的深度，就是其左右子节点的深度最大值加1即可，为什么加1，要加上本身这一层。那我们左右子节点深度怎么求，是不是也是以左右子节点为根节点求深度，那就很显着了，递归的参数不就是其左节点或者右节点嘛，返回值当然就是深度了。
  
• 确定递归的制止条件：什么时候制止，这里来看，当节点为空返回零就行了，表示高度为0。
  
• 确定单层递归的逻辑：单层递归的逻辑就是很简单的，我们求其左节点的深度，在求其右节点的深度，取最大的加1就行了，就是当前节点的深度了。
  

1. class Solution:
2.     def maxdepth(self, root: treenode) -> int:
3.         return self.getdepth(root)
4.         
5.     def getdepth(self, node):
6.         if not node:
7.             return 0
8.         leftheight = self.getdepth(node.left) #左
9.         rightheight = self.getdepth(node.right) #右
10.         height = 1 + max(leftheight, rightheight) #中
11.         return height

复制代码

二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

相关本领：这道题同样很熟悉，也是我们之前讲层序遍历的时候学习过的，这下我们来看看如何使用递归的方法解这道题。求深度高度这种是不是就是只要左右子树的深度的最大值加1就是当前节点的深度高度了，那么递归下去是不是就可以求出根节点的深度了，不外这道题有点差别哦，我们要求的是最小深度。同样的我们来看递归三要素：

• 确定递归的参数和返回值：跟求最大深度的处理方式是雷同的，我们传入的参数就是节点，返回数值即高度。
  
• 确定递归的制止条件：什么时候制止，这里来看，当节点为空返回零就行了，表示高度为0。
  
• 确定单层递归的逻辑：单层递归的逻辑这里就与求最大深度差别了，我们要看我们是要找最近的叶子节点的深度，那么如果按照之前的直接改成求min来做会出现错误，当没有左子树有右子树的时候就会返回零，但是其不是叶子节点就会发生歧义。以是我们这里处理就是无左节点，有右节点的时候返回右边的最小，同样的无右节点，有左节点的时候返回左边的最小即可
  

1. class Solution:
2.     def getDepth(self, node):
3.         if node is None:
4.             return 0
5.         leftDepth = self.getDepth(node.left)  # 左
6.         rightDepth = self.getDepth(node.right)  # 右
7.         
8.         # 当一个左子树为空，右不为空，这时并不是最低点
9.         if node.left is None and node.right is not None:
10.             return 1 + rightDepth
11.         
12.         # 当一个右子树为空，左不为空，这时并不是最低点
13.         if node.left is not None and node.right is None:
14.             return 1 + leftDepth
15.         
16.         result = 1 + min(leftDepth, rightDepth)
17.         return result
19.     def minDepth(self, root):
20.         return self.getDepth(root)

复制代码

完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

相关本领：这道题还是比较简单的，我们直接看就行，实在其做法与求最大深度是很像的，就是左子树的节点个数加上右节点的节点个数就行了：

• 确定递归的参数和返回值：传入节点，求节点个数，返回数值，节点的个数。
  
• 确定递归的制止条件：什么时候制止，这里来看，当节点为空返回零就行了，表示节点个数为0。
  
• 确定单层递归的逻辑：单层递归的逻辑就是我们求左子树的节点个数加右节点的节点个数，两者相加再加1，加上自己本身的一个节点，就是当前的节点个数了。
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def countNodes(self, root: Optional[TreeNode]) -> int:
9.         if not root:
10.             return 0
12.         leftnums=self.countNodes(root.left)
13.         rightnums=self.countNodes(root.right)
14.         nums=leftnums+rightnums+1
15.         return nums

复制代码

平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

相关本领：首先我们的明确平衡二叉树的定义是什么，即其左右子树的高度差不能大于1。那么我们就能明确我们需要去做些什么了。找出左子树的高度和右子树的高度二者做差取绝对值即可。

• 确定递归的参数和返回值：按照我们需要去做的，传入的参数就是其左右子节点，返回值即两者的高度。
  
• 确定递归的制止条件：什么时候制止，这里来看，当节点为空返回零就行了，表示高度为0。
  
• 确定单层递归的逻辑：我们找出左子树的高度和右子树的高度，当差的绝对值大于1即不符合定义返回-1，或者其左子树和右子树已经有不满意定义的情况直接返回-1，符合条件就返回高度即可。
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def isBalanced(self, root: Optional[TreeNode]) -> bool:
9.         return self.get_hight(root) != -1
10.     def get_hight(self, node):
11.         if not node:
12.             return 0
13.         left = self.get_hight(node.left)
14.         right = self.get_hight(node.right)
15.         if left == -1 or right == -1 or abs(left - right) > 1:
16.             return -1
17.         return max(left, right) + 1

复制代码

二叉树的全部路径

257. 二叉树的全部路径 - 力扣（LeetCode）

相关本领：找出路径，就是我们要一直到达叶子节点才行，那么这里我们会用到回溯的思想。由于我们会有变量来保存路径，当达到叶子节点输出该路径后，我们需要从路径中回溯上个节点的情况，要否则下个叶子节点的输出会带上这个叶子节点，这就是有问题的了。

• 确定递归的参数和返回值：我们需要当前的节点，一个保存路径的path，一个保存结果的result。返回值这里有没有都行，由于我们已经用result来保存结果了。
  
• 确定递归的制止条件：当到达叶子节点就可以制止了，即其节点左右子节点为空。
  
• 确定单层递归的逻辑：当左右节点存在就进入，同时这里要留意结束递归后要紧跟回溯，回溯是跟递归一一对应的。
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def traversal(self, cur, path, result):
9.         path.append(cur.val)
10.         if cur.left == None and cur.right == None:
11.             sPath='->'.join(map(str,path))
12.             result.append(sPath)
13.         if cur.left:
14.             self.traversal(cur.left,path,result)
15.             path.pop()
16.         if cur.right:
17.             self.traversal(cur.right,path,result)
18.             path.pop()
20.     def binaryTreePaths(self, root):
21.         result = []
22.         path = []
23.         if not root:
24.             return result
25.         self.traversal(root, path, result)
26.         return result

复制代码

左叶子之和

404. 左叶子之和 - 力扣（LeetCode）

• 相关本领：这里的难点就是我们该怎么去判断是不是左叶子节点，留意是左叶子节点，而不是左节点。判断其是不是左叶子节点，我们需要通过其父节点才可以大概来判断
  
  
  
  • 确定递归的参数和返回值：递归的参数就是节点，由于我们需要去判断是不是左叶子节点。返回值就是其左叶子节点的值
    
  • 确定递归的制止条件：当节点为空，或者其左右子节点为空就可制止，由于我们得通过父节点来判断，以是到这就可制止了。
    
  • 确定单层递归的逻辑：我们需要判断其左节点是不是叶子节点，是就保留其值举行累加，右子树同样的操作，只判断其是否有左叶子节点。
    
  
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def sumOfLeftLeaves(self, root):
9.         if root is None:
10.             return 0
11.         if root.left is None and root.right is None:
12.             return 0
13.         
14.         leftValue = self.sumOfLeftLeaves(root.left)  # 左
15.         if root.left and not root.left.left and not root.left.right:  # 左子树是左叶子的情况
16.             leftValue = root.left.val
17.             
18.         rightValue = self.sumOfLeftLeaves(root.right)  # 右
20.         sum_val = leftValue + rightValue  # 中
21.         return sum_val

复制代码

找树左下角的值

513. 找树左下角的值 - 力扣（LeetCode）

相关本领：我们要找左下角的值，看清题目是左下角，并不是我们一直找左节点就行了的，也同样可能会在右子树的左节点的，以是我们观察其特性，其一定会出如今最深的一层的叶子节点中，以是我们就可以来解题目了。

• 确定递归的参数和返回值：传入的就是节点和深度，通过最深的一层的叶子节点来判断，返回值就是其节点的值
  
• 确定递归的制止条件：当到达叶子节点就可以制止了。
  
• 确定单层递归的逻辑：左节点存在就进入直到叶子节点，同样的留意递归结束后，我们的深度需要回溯到其本来的值即减一即可，由于我们还要去右节点中举行寻找。
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def findBottomLeftValue(self, root: TreeNode) -> int:
9.         self.max_depth = float('-inf')
10.         self.result = None
11.         self.traversal(root, 0)
12.         return self.result
13.    
14.     def traversal(self, node, depth):
15.         if not node.left and not node.right:
16.             if depth > self.max_depth:
17.                 self.max_depth = depth
18.                 self.result = node.val
19.             return
20.         
21.         if node.left:
22.             depth += 1
23.             self.traversal(node.left, depth)
24.             depth -= 1
25.         if node.right:
26.             depth += 1
27.             self.traversal(node.right, depth)
28.             depth -= 1

复制代码

路径总和

112. 路径总和 - 力扣（LeetCode）

相关本领：练习过前面的题目后这道题就比较简单了，直接来看递归三要素

• 确定递归的参数和返回值：递归的参数就是节点，以及我们用来纪录值的count，返回值就是存在与否即true或者false
  
• 确定递归的制止条件：当count为0的时候而且到达了叶子节点即返回true，或者达到叶子节点count并未为0即返回false
  
• 确定单层递归的逻辑：左节点存在就进入，count减去当前值，递归结束后要加回来，即回溯的过程。
  

1. # Definition for a binary tree node.
2. # class TreeNode:
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:
8.     def traversal(self, cur: TreeNode, count: int) -> bool:
9.         if not cur.left and not cur.right and count == 0: # 遇到叶子节点，并且计数为0
10.             return True
11.         if not cur.left and not cur.right: # 遇到叶子节点直接返回
12.             return False
13.         
14.         if cur.left: # 左
15.             count -= cur.left.val
16.             if self.traversal(cur.left, count): # 递归，处理节点
17.                 return True
18.             count += cur.left.val # 回溯，撤销处理结果
19.             
20.         if cur.right: # 右
21.             count -= cur.right.val
22.             if self.traversal(cur.right, count): # 递归，处理节点
23.                 return True
24.             count += cur.right.val # 回溯，撤销处理结果
25.             
26.         return False
27.    
28.     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
29.         if root is None:
30.             return False
31.         return self.traversal(root, targetSum - root.val)  

复制代码

算法基础系列

一文相识什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇-CSDN博客
【双指针法】:这么常用的你怎么能不知道-CSDN博客
【二叉树】理论基础篇1-CSDN博客
【二叉树】实战篇1-CSDN博客

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。