Jul 23, 2022 · Jul 23, 2022
diff --git a/...leetcode/editor/cn/doc/[124]二叉树中的最大路径和.py → script/[124]二叉树中的最大路径和.py b/...leetcode/editor/cn/doc/[124]二叉树中的最大路径和.py → script/[124]二叉树中的最大路径和.py
 #  提示：
 #
 #
 #  树中节点数目范围是 [1, 3 *10⁴]
 #  树中节点数目范围是 [1, 3 *104]
 #  -1000 <= Node.val <= 1000
 #
 #  Related Topics 树 深度优先搜索 动态规划 二叉树 👍 1657 👎 0
 #  Related Topics 树 深度优先搜索 动态规划 二叉树
 #  👍 1663 👎 0


 # leetcode submit region begin(Prohibit modification and deletion)
 #         self.right = right
 class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        maxpath = -2**31

        def dfs(root):
            nonlocal maxpath
            if not root:
                return 0
            left = max(dfs(root.left),0)
            right = max(dfs(root.right),0)
            maxpath = max(left+right+root.val, maxpath)
            return max(left, right) + root.val
        dfs(root)
        return maxpath
 # leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/[654]最大二叉树.py b/script/[654]最大二叉树.py
 # 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 #
 #
 #  创建一个根节点，其值为 nums 中的最大值。
 #  递归地在最大值 左边 的 子数组前缀上 构建左子树。
 #  递归地在最大值 右边 的 子数组后缀上 构建右子树。
 #
 #
 #  返回 nums 构建的 最大二叉树 。
 #
 #
 #
 #  示例 1：
 #
 #
 # 输入：nums = [3,2,1,6,0,5]
 # 输出：[6,3,5,null,2,0,null,null,1]
 # 解释：递归调用如下所示：
 # - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 #     - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 #         - 空数组，无子节点。
 #         - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 #             - 空数组，无子节点。
 #             - 只有一个元素，所以子节点是一个值为 1 的节点。
 #     - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 #         - 只有一个元素，所以子节点是一个值为 0 的节点。
 #         - 空数组，无子节点。
 #
 #
 #  示例 2：
 #
 #
 # 输入：nums = [3,2,1]
 # 输出：[3,null,2,null,1]
 #
 #
 #
 #
 #  提示：
 #
 #
 #  1 <= nums.length <= 1000
 #  0 <= nums[i] <= 1000
 #  nums 中的所有整数 互不相同
 #
 #  Related Topics 栈 树 数组 分治 二叉树 单调栈
 #  👍 460 👎 0


 # leetcode submit region begin(Prohibit modification and deletion)
 # Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, val=0, left=None, right=None):
 #         self.val = val
 #         self.left = left
 #         self.right = right
 classSolution:
 defconstructMaximumBinaryTree(self,nums:List[int])->TreeNode:
 defdfs(start,end):
 ifstart>end:
 returnNone
 ifstart==end:
 returnTreeNode(nums[start])
 maxval=max(nums[start:(end+1)])
 pos=nums.index(maxval)
 root=TreeNode(maxval)
 root.left=dfs(start,pos-1)
 root.right=dfs(pos+1,end)
 returnroot
 returndfs(0,len(nums)-1)
 # leetcode submit region end(Prohibit modification and deletion)
diff --git a/script/leetcode/editor/cn/doc/[110]平衡二叉树.py b/script/leetcode/editor/cn/doc/[110]平衡二叉树.py
diff --git a/script/leetcode/editor/cn/doc/[173]二叉搜索树迭代器.py b/script/leetcode/editor/cn/doc/[173]二叉搜索树迭代器.py
diff --git a/树总结.md b/树总结.md
 2. 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归


 ### 437 路经总和III

 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。



 示例 1：

 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
 输出：3
 解释：和等于 8 的路径有 3 条，如图所示。

 示例 2：

 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 输出：3



 提示:

    二叉树的节点个数的范围是 [0,1000]
    -109 <= Node.val <= 109
    -1000 <= targetSum <= 1000



 1. 两层递归

 ```python
 # Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, val=0, left=None, right=None):
 #         self.val = val
 #         self.left = left
 #         self.right = right
 class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        if not root:
            return 0
        def dfs(root, target):
            if not root:
                return 0
            if target==root.val:
                mid = 1
            else:
                mid =0
            left = dfs(root.left, target-root.val)
            right = dfs(root.right, target-root.val)
            return mid+left+right
        return dfs(root, targetSum)+self.pathSum(root.left, targetSum)+ self.pathSum(root.right, targetSum)

 ```



 Tips

 1. 内层递归就是常规的路径求和，区别在于不再中间停止，只在中间记录等于target的路径进行累加
 2. 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归



 ### 450. 删除二叉搜索树中的节点.md
 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
Original file line number	Diff line number	Diff line change
Expand Up		@@ -27,10 +27,11 @@
		# 提示：
		#
		#
		# 树中节点数目范围是 [1, 3 *10⁴]
		# 树中节点数目范围是 [1, 3 *104]
		# -1000 <= Node.val <= 1000
		#
		# Related Topics 树深度优先搜索动态规划二叉树 👍 1657 👎 0
		# Related Topics 树深度优先搜索动态规划二叉树
		# 👍 1663 👎 0


		# leetcode submit region begin(Prohibit modification and deletion)
Expand All		@@ -42,4 +43,16 @@
		# self.right = right
		class Solution:
		def maxPathSum(self, root: Optional[TreeNode]) -> int:
		maxpath = -2**31

		def dfs(root):
		nonlocal maxpath
		if not root:
		return 0
		left = max(dfs(root.left),0)
		right = max(dfs(root.right),0)
		maxpath = max(left+right+root.val, maxpath)
		return max(left, right) + root.val
		dfs(root)
		return maxpath
		# leetcode submit region end(Prohibit modification and deletion)
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,71 @@
		# 给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:
		#
		#
		# 创建一个根节点，其值为 nums 中的最大值。
		# 递归地在最大值左边的子数组前缀上构建左子树。
		# 递归地在最大值右边的子数组后缀上构建右子树。
		#
		#
		# 返回 nums 构建的最大二叉树。
		#
		#
		#
		# 示例 1：
		#
		#
		# 输入：nums = [3,2,1,6,0,5]
		# 输出：[6,3,5,null,2,0,null,null,1]
		# 解释：递归调用如下所示：
		# - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
		# - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
		# - 空数组，无子节点。
		# - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
		# - 空数组，无子节点。
		# - 只有一个元素，所以子节点是一个值为 1 的节点。
		# - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
		# - 只有一个元素，所以子节点是一个值为 0 的节点。
		# - 空数组，无子节点。
		#
		#
		# 示例 2：
		#
		#
		# 输入：nums = [3,2,1]
		# 输出：[3,null,2,null,1]
		#
		#
		#
		#
		# 提示：
		#
		#
		# 1 <= nums.length <= 1000
		# 0 <= nums[i] <= 1000
		# nums 中的所有整数互不相同
		#
		# Related Topics 栈树数组分治二叉树单调栈
		# 👍 460 👎 0


		# leetcode submit region begin(Prohibit modification and deletion)
		# Definition for a binary tree node.
		# class TreeNode:
		# def __init__(self, val=0, left=None, right=None):
		# self.val = val
		# self.left = left
		# self.right = right
		classSolution:
		defconstructMaximumBinaryTree(self,nums:List[int])->TreeNode:
		defdfs(start,end):
		ifstart>end:
		returnNone
		ifstart==end:
		returnTreeNode(nums[start])
		maxval=max(nums[start:(end+1)])
		pos=nums.index(maxval)
		root=TreeNode(maxval)
		root.left=dfs(start,pos-1)
		root.right=dfs(pos+1,end)
		returnroot
		returndfs(0,len(nums)-1)
		# leetcode submit region end(Prohibit modification and deletion)
Original file line number	Diff line number	Diff line change
Expand Up		@@ -2273,6 +2273,71 @@ Tips
		2. 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归


		### 437 路经总和III

		给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

		路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。



		示例 1：

		输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
		输出：3
		解释：和等于 8 的路径有 3 条，如图所示。

		示例 2：

		输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
		输出：3



		提示:

		二叉树的节点个数的范围是 [0,1000]
		-109 <= Node.val <= 109
		-1000 <= targetSum <= 1000



		1. 两层递归

		```python
		# Definition for a binary tree node.
		# class TreeNode:
		# def __init__(self, val=0, left=None, right=None):
		# self.val = val
		# self.left = left
		# self.right = right
		class Solution:
		def pathSum(self, root: TreeNode, targetSum: int) -> int:
		if not root:
		return 0
		def dfs(root, target):
		if not root:
		return 0
		if target==root.val:
		mid = 1
		else:
		mid =0
		left = dfs(root.left, target-root.val)
		right = dfs(root.right, target-root.val)
		return mid+left+right
		return dfs(root, targetSum)+self.pathSum(root.left, targetSum)+ self.pathSum(root.right, targetSum)

		```



		Tips

		1. 内层递归就是常规的路径求和，区别在于不再中间停止，只在中间记录等于target的路径进行累加
		2. 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归



		### 450. 删除二叉搜索树中的节点.md
		给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

Expand Down