二叉树算法

二叉树的递归遍历

代码：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


# 前序遍历-递归-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root) :
        # 保存结果
        result = []
        def traversal(root):
            if root == None:
                return
            result.append(root.val)  # 前序
            traversal(root.left)  # 左
            traversal(root.right)  # 右

        traversal(root)
        return result


# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root) :
        result = []
        def traversal(root):
            if root == None:
                return
            traversal(root.left)  # 左
            result.append(root.val)  # 中序
            traversal(root.right)  # 右

        traversal(root)
        return result


# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root) :
        result = []

        def traversal(root):
            if root == None:
                return
            traversal(root.left)  # 左
            traversal(root.right)  # 右
            result.append(root.val)  # 后序

        traversal(root)
        return result

二叉树的迭代遍历

代码：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root) :
        # 根结点为空则返回空列表
        if not root:
            return []
        stack=[root]
        result=[]
        while stack:
            node=stack.pop()
            result.append(node.value)
            if root.right:
                stack.append(root.right)
            if root.left:
                stack.append(root.left)
        return result



# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root) :
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:
                stack.append(cur)
                cur = cur.left
            # 到达最左结点后处理栈顶结点
            else:
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right
        return result

# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root):
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 左孩子先入栈
            if node.left:
                stack.append(node.left)
            # 右孩子后入栈
            if node.right:
                stack.append(node.right)
        # 将最终的数组翻转
        return result[::-1]

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思路：

• 使用队列的先进先出来存储遍历
• 层次的思想，每轮迭代去size大小的队列元素
• 判断队列元素是否有左右子树，有则添加在队列末尾
• 直到队列为空，遍历结束

代码：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    """二叉树层序遍历迭代解法"""
    def levelOrder(root):
        results = []
        if not root:
            return results

        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.value)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        return results

107.二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思路：

• 将二叉树的层序遍历结果逆序输出

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    """二叉树层序遍历迭代解法"""
    def levelOrderBottom(self,root):
        results = []
        if not root:
            return results

        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        return results[::-1]

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

思路：

• 二叉树层序遍历
• 返回每一层的最后一个元素

代码：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    """二叉树层序遍历迭代解法"""

    def rightSideView(root):
        if not root:
            return []
        result=[]
        from collections import deque
        que=deque([root])
        while que:
            size=len(que)
            for _ in range(size):
                cur=que.popleft()
                if _==size-1:
                    result.append(cur.value)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return result

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

思路：

该题主要改变原有完美二叉树的每层最后一个节点的指向

由于该完美二叉树的每个结点定义除了left，right还有next，不定义next时，指向为空

当检索到最后一个节点时，退出层级

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
        self.next=None


class Solution:
    """二叉树层序遍历迭代解法"""

    def connect(root):
        if not root:
            return root

        from collections import deque
        que = deque([root])
        while que:
            size = len(que)
            for _ in range(size):
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                if _ ==size -1:
                    break
                cur.next=que[0]
        return root

117.填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

输入：root = []
输出：[]

思路：

• 代码完全没有改变
• 从完美二叉树到二叉树
• 还是根据层级的考虑

代码：

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
        self.next=None


class Solution:
    """二叉树层序遍历迭代解法"""

    def connect(root):
        if not root:
            return root

        from collections import deque
        que = deque([root])
        while que:
            size = len(que)
            for _ in range(size):
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                if _ ==size -1:
                    break
                cur.next=que[0]
        return root

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

思路：

计算层级的个数 就是最大深度

代码：

class Solution:
    """二叉树层序遍历迭代解法"""

    def maxDepth(root):
        if not root:
            return 0

        from collections import deque
        que=deque([root])
        depth=0
        while que:
            depth+=1
            size=len(que)
            for _ in range(size):
                cur=que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return depth

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

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

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

思路：

层级遍历

判断某个节点是否有左右节点如果没有左右节点，则是最小深度

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    """二叉树层序遍历迭代解法"""

    def minDepth(root):
        if not root:
            return 0

        from collections import deque
        que=deque([root])
        depth=0
        mindepth=float('inf')
        while que:
            size=len(que)
            depth+=1
            for _ in range(size):
                cur=que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                if not cur.left and not cur.right:
                    mindepth=depth
                    return mindepth

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

思路：

递归：

• 参数和返回值都是root，主要是对以根节点为首的树的操作
• 结束条件是如果遍历的root值为空，就结束
• 逻辑业务方面是调换left和right同时进行递归

迭代：

• 采用前序遍历的方式进行遍历，对每个节点进行left，right调换
• 再分别对右子树左子树入栈

代码：

# 递归
class Solution:
    def invertTree(self,root):
        if not root:
            return None
        root.left,root.right=root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

# 迭代
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None
        
        stack = [root]
        
        while stack:
            # 当前节点出栈
            node = stack.pop()
            # 将当前节点的左右子树交换
            node.left, node.right = node.right, node.left
            
            # 右子树入栈
            if node.right:
                stack.append(node.right)
            # 左子树入栈
            if node.left:
                stack.append(node.left)
            
        return root

101.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

思路：

层序遍历：

根据层序遍历，获取每一层的数组

采用双指针法对数组进行首尾比较

迭代法：

传入参数为左右指针，返回参数为bool

结束条件为如果左空右不空、右空左不空、左右非空且值不同，则为false，如果左右都是空，则为true

如果左右对应的值相同，进入逻辑层

判断外层以及内层的递归

代码：

# 递归
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.compare(root.left, root.right)

    def compare(self, left, right):
        # 首先排除空节点的情况
        if left == None and right != None:
            return False
        elif left != None and right == None:
            return False
        elif left == None and right == None:
            return True

        # 排除了空节点，再排除数值不相同的情况
        elif left.val != right.val:
            return False

        # 此时就是：左右节点都不为空，且数值相同的情况
        # 此时才做递归，做下一层的判断
        outside = self.compare(left.left, right.right)  # 左子树：左、 右子树：右
        inside = self.compare(left.right, right.left)  # 左子树：右、 右子树：左
        isSame = outside and inside  # 左子树：中、 右子树：中 （逻辑处理）
        return isSame

class Solution:
    """二叉树层序遍历迭代解法"""

    def isSymmetric(self,root):
        results = []
        if not root:
            return True
        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                if not cur:
                    result.append('null')
                else:
                    result.append(cur.val)
                
                    que.append(cur.left)
                
                    que.append(cur.right)
            left=0
            right=len(result)-1
            while left<right:
                if result[left]==result[right]:
                    left+=1
                    right-=1
                else:
                    return False
        return True

257.二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

思路：

• 注意：数组作为参数来进行值传递
• 采用递归的方式：
• 结束条件为无左右结点，此时对result添加值
• 业务逻辑就是遍历

代码：

class Solution:
    def binaryTreePaths(self, root) :
        result=[]
        path=''
        if not root: return result
        self.traversal(root,path,result)
        return result
    
    def traversal(self,cur,path,result):
        path+=str(cur.val)
        if not cur.left and not cur.right:
            result.append(path)
        if cur.left:
            self.traversal(cur.left,path+'->',result)
        if cur.right:
            self.traversal(cur.right,path+'->',result)

112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

思路：

跟上题类似，上题是求所有路径的向量表示

这题是求所有路径的结点的sum值

代码：

class Solution:
    def hasPathSum(self,root, targetSum):
        if not root:
            return False
        sum1 = 0
        results = []

        def fn(root, sum1, results):
            sum1 += root.val
            if root.left == None and root.right == None:
                results.append(sum1)
            if root.left:
                fn(root.left, sum1, results)
            if root.right:
                fn(root.right, sum1, results)

        fn(root, sum1, results)

        return True if targetSum in results else False

106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

代码：

class Solution:
    def buildTree(self, inorder, postorder):
        # 第一步: 特殊情况讨论: 树为空. 或者说是递归终止条件
        if not postorder:
            return

        # 第二步: 后序遍历的最后一个就是当前的中间节点
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 第三步: 找切割点.
        root_index = inorder.index(root_val)

        # 第四步: 切割inorder数组. 得到inorder数组的左,右半边.
        left_inorder = inorder[:root_index]
        right_inorder = inorder[root_index + 1:]

        # 第五步: 切割postorder数组. 得到postorder数组的左,右半边.
        # ⭐️ 重点1: 中序数组大小一定跟后序数组大小是相同的.
        left_postorder = postorder[:len(left_inorder)]
        right_postorder = postorder[len(left_inorder): len(postorder) - 1]


        # 第六步: 递归
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)

        # 第七步: 返回答案
        return root

654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 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]

思路：

对数组的操作，取数组的最大值并获得数组最大值的index，

取index左侧的为树的左子树结点构造

取index右侧的数组作为树的右子树构造

采用递归的方式进行构造

代码：

class Solution:
    """递归法 更快"""
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        maxvalue = max(nums)
        index = nums.index(maxvalue)
        
        root = TreeNode(maxvalue)

        left = nums[:index]
        right = nums[index + 1:]

        root.left = self.constructMaximumBinaryTree(left)
        root.right = self.constructMaximumBinaryTree(right)
        return root

617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

思路：

采用递归的思路

结束条件：如果root1为空，返回root2，如果root2为空，返回root1

逻辑层：两则都不为空，对应的val值相加

代码：

class Solution:
    def mergeTrees(self, root1, root2):
        if not root1:
            return root2
        if not root2:
            return root1
        root1.val+=root2.val
        root1.left=self.mergeTrees(root1.left,root2.left)
        root1.right=self.mergeTrees(root1.right,root2.right)
        return root1

700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

思路：

本身还是对二叉树的遍历，采用前序遍历的方式，使用递归的方法

如果当前结点的值等于target 返回当前结点

如果小于递归当前结点的左节点

如果大于递归当前结点的右节点

代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def searchBST(self, root, val):
        if not root:
            return None
        if root.val==val:
            return root
        if root.val>val:
            return self.searchBST(root.left,val)
        else:
            return self.searchBST(root.right,val)

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

思路：

对该二叉树进行中序遍历，遍历的结果为递增

判断是否为递增

代码：

# 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 isValidBST(self, root):
        #中序遍历
        stack=[]
        pre=None
        cur=root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur=cur.left
            else:
                cur=stack.pop()
                if pre and cur.val<=pre.val:
                    return False
                pre=cur
                cur=cur.right
        return True

530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

思路：

二叉搜索树 通过中序遍历获得遍历数组

比较遍历数组的相邻的两数的绝对值之差 取最小值

代码：

class Solution:
    def getMinimumDifference(self,root):
        result=[]
        record=[]
        self.zhongxu(root,result)
        for i in range(len(result)-1):
            record.append(abs(result[i+1]-result[i]))
        return min(record)

    def zhongxu(self,root,result):
        if not root:
            return None
        self.zhongxu(root.left,result)
        result.append(root.val)
        self.zhongxu(root.right,result)

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

思路：

统计二叉搜索树中val值出现的次数

对次数进行排序如有相同一起输出

代码：

class Solution:
    def findMode(self,root):
        result = []
        self.zhongxu(root, result)
        record = {}
        for i in result:
            if i in record:
                record[i] += 1
            else:
                record[i] = 1
        tuplelist = [(val, key) for key, val in record.items()]
        tuplelist_sorted = sorted(tuplelist, reverse=True)
        target = tuplelist_sorted[0][0]
        res = []
        for j in tuplelist_sorted:
            if j[0] == target:
                res.append(j[1])
            else:
                break
        return res
    def zhongxu(self,root, result):
        if not root:
            return None
        self.zhongxu(root.left, result)
        result.append(root.val)
        self.zhongxu(root.right, result)

701.二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

思路：

采用递归法

结束条件 递归到None时 创建新结点

逻辑层 判断结点的值跟val值的比较 实行递归

代码：

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:
            node = TreeNode(val)
            return node

        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)

        return root

450.删除二叉搜索树中的节点

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

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

代码：

class Solution:
    def deleteNode(self, root:TreeNode, key: int) :
        if not root: return None
        if key>root.val:
            root.right=self.deleteNode(root.right,key)
        elif key<root.val:
            root.left=self.deleteNode(root.left,key)
        else:
            if not root.right:
                return root.left
            if not root.left:
                return root.right
            node=root.right # 找到右节点的最左侧结点
            while node.left:
                node=node.left
            node.left=root.left# 将root.left连接到刚刚找到的右侧最左侧结点
            root=root.right# 用root.right代替root
        return root