【代码随想录】【二叉树】day18:二叉树的左下角的值，路径总和、构造二叉树

本文主要是介绍【代码随想录】【二叉树】day18:二叉树的左下角的值，路径总和、构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1二叉树左下角的值

左下角的值：最后一层最左侧的节点的值

递归

from collections import deque
class TreeNode:def __init__(self,val,left=None,right=None):self.val = valself.left = leftself.right = rightclass solution:def leftBottomNode(self,root):self.maxdepth=0self.result=Noneself.travelsal(root,0)return self.resultdef travelsal(self,root:TreeNode,depth):# 终止条件：遍历到深度最大的节点了if root.left is None and root.right is None:if depth >self.maxdepth:self.maxdepth=depthself.result= root.val# 单层递归逻辑# 左 因为这里的return不在中，即没有处理中的逻辑，而我们需要记录递归时的深度，所以深度这个变量不是从上一层返回递增的，而是需要回溯if root.left:depth+=1self.travelsal(root.left,depth)depth-=1if root.right:depth+=1self.travelsal(root.right,depth)depth-=1

层序遍历

每层队列第一个popleft的值就是每层最左边的值，不断更新这个result找到左下角的值

   def leftBottomNode2(self,root):if root is not None:que=deque()que.append(root)result=0while len(que)>0:size=len(que)vec = []while size:result=que.popleft().valsize-=1if root.left:que.append(root.left)if root.right:que.append(root.right)

2路径总和

代码随想录

第一种递归函数需要返回值的情况：力扣

该题在遍历过程中需要及时返回true 或者false以停止继续搜索

def findSumTree(self,root:TreeNode,count)->bool:# 终止条件 按照count--的做法if root is None:return Falseif root.left is None and root.right is None and count==0:return Trueif root.left is None and root.right is None and count!=0:return Falseif root.left:count-=root.left.val# 什么时候需要返回值，什么时候不需要返回值if (self.findSumTree(root.left,count)):# 递归时需要及时返回return Truecount+=root.left.valif root.right:count-=root.right.valif (self.findSumTree(root.right,count)):return Truecount+=root.right.val

第二种递归函数不需要返回值的情况：

class solution2:def __init__(self):self.result=[]self.path=[]def findSumTree2(self,root:TreeNode,count)->bool:# 终止条件 按照count--的做法if root is None:return Falseif root.left is None and root.right is None and count==0:# Python里不写[:]代表的是传的是引用，会变，带上就是拷贝的结果，相当于快照self.result.append(self.path[:])return self.resultif root.left is None and root.right is None and count!=0:return Falseif root.left:count-=root.left.valself.path.append(root.left.val)# 什么时候需要返回值，什么时候不需要返回值self.findSumTree2(root.left,count)count+=root.left.val  # 两次回溯self.path.pop()if root.right:count-=root.right.valself.path.append(root.right.val)self.findSumTree2(root.right,count)count+=root.right.valself.path.pop()return self.resultdef getSumTree(self,root,sum):if root is None:return 0self.path.append(root.val)return self.findSumTree2(root,sum-root.val)

3构造二叉树

中序和后序可以构造二叉树
中序和前序也可以构造二叉树
但是前序和后序不能构造二叉树，因为找不到根节点的位置

from typing import List
from collections import deque
class TreeNode:def __init__(self,val,left=None,right=None):self.val = valself.left = leftself.right = rightclass solution:# 中序和后序def createTree(self,inorder:List[int],postorder:List[int]):# 终止条件if len(inorder) == 0:return None# 先从后序数组里找中节点root = TreeNode(postorder[-1])# 然后找到中序数组里中节点的indexindex = inorder.index(root.val)# 确定中序数组的左子树和右子树inorder_left=inorder[:index]inorder_right=inorder[index+1:]# 然后递归处理左子树和右子树'''一定要保证递归的两个数组的长度是相同的'''root.left = self.createTree(inorder[:index],postorder[:len(inorder_left)])# 正常来讲 postorder应该从len(inorder_left)+1开始，但是要保证二者的长度相同，所以从len(inorder_left)开始root.right = self.createTree(inorder[index+1:],postorder[len(inorder_left):-1])return rootdef bulidTree(self,preorder,inorder):if len(preorder) == 0:return None# 从前序数组里找根节点root = TreeNode(preorder[0])index = inorder.index(root.val)'''一定要保证递归的两个数组的长度是相同的'''root.left = self.bulidTree(preorder[1:index+1],inorder[:index])root.right = self.bulidTree(preorder[index+1:],inorder[index+1:])return rootdef preorderPrint(self, root:TreeNode):if root is None:return []print(root.val)left=self.preorderPrint(root.left)right=self.preorderPrint(root.right)def travelsal(self,root:TreeNode):if root is not None:que=deque()que.append(root)result=[]# 一定是while，不是ifwhile len(que)>0:size=len(que)vec = []while size:root=que.popleft()vec.append(root.val)size-=1if root.left:que.append(root.left)if root.right:que.append(root.right)result.append(vec)return result