递归

这里对递归的掌握十分的重要，后面很多的思想和题目都是来自于递归的方法，所以自己必须狠狠的啃下来，理解下来，而且要从本质上去理解递归，用的实在是太多的地方了（二次回顾的时候就再次强调这里的内容了）!!!!!!

内涵：

1. 从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件
2. 把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
3. 递归需要用到栈的调用，而对栈的理解又是一大核心
   参考链接：
   https://blog.csdn.net/weixin_44143702/article/details/86551826
   https://www.bilibili.com/video/BV1B4411H76f?p=43
   https://www.cnblogs.com/kubidemanong/p/10538799.html

满足的条件：

1. 必须包含一个明确的递归的结束条件（也即递归的出口或者是边界）
2. 自己调用自己:在一个函数的定义中又直接或间接的调用本身

递归需要遵守的一些重要的规则：

1. 执行一个方法的时候，就会创建一个新的受保护的独立空间（栈空间）
2. 方法的局部变量是独立的，不会受影响
3. 递归必须向退出递归的条件逼近，否则就是无限循环
4. 当一个方法执行完毕或者遇到return，就会返回。遵守谁调用就将结果返回给谁，同时当方法执行完毕或返回的时候，该方法也会执行完毕。

递归的优缺点：

优点：符合人的思维方式，递归程序结构清晰，可读性，容易理解
缺点：通过调用函数实现，当递归层数过多时，程序的效率低

递归的应用场景：

1. 数据的定义形式是递归的，例如求Fibonacii数列的第n项
2. 数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作
3. 某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一组操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束。例如：汉诺塔问题。

递归常常的一些问题以及算法：（基础中的基础部分）

1. 8皇后问题
2. 汉诺塔问题
3. 迷宫问题
4. 球和篮子的问题
5. 阶乘问题
6. 归并排序
7. 二分查找
8. 分治算法
9. 用栈解决的问题，递归代码比较的简洁

真正自己在用递归的时候需要强迫自己思考的几个步骤

1. 明确这个函数想要干什么？（第一步就在这，有了方向就有了接下来的实现）
2. 寻找递归结束条件（这里的结束条件可能不止一个，需要通过第三不进行反推）
3. 找出函数的等价关系式

还是得熟悉几个递归的小例子

写在前面：多思考，多总结，多练习，多调试

python二叉树类定义

列表转二叉树，leetcode本地调试的方法：（自己暂时没有解决这个问题）
链接：https://blog.csdn.net/qq_35376241/article/details/106070293,后面自己有精力自己琢磨一下
https://vimsky.com/examples/detail/python-ex-TreeNode-TreeNode-fromArray-method.html这篇文章后面自己也可以参考一下
https://blog.csdn.net/Mr_111000/article/details/119680459这篇里面也写得不错

1. 通过二叉树的类定义
2. 通过将列表转化为二叉树

class TreeNode:
   """ 定义树的节点类型 """
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def makeTree(l:List) -> TreeNode:
    """ 由输入列表生成树，返回根节点 """
    q = []
    if not l:
        return
    root = TreeNode(val=l.pop(0))
    q.append(root)
    while q:
        t = q.pop(0)
        if l:
            if l[0] != 'null':
                t.left = TreeNode(val=l.pop(0))
                q.append(t.left)
            else:
                l.pop(0)
        if l:
            if l[0] != 'null':
                t.right = TreeNode(val=l.pop(0))
                q.append(t.right)
            else:
                l.pop(0)
    return root

# 将列表转换为二叉树
class List2Tree(object):
 
    def __init__(self, nums: list):
        self.nums = nums
        self.queue = []
        if len(nums) == 1:
            self.root = TreeNode(self.nums.pop(0))
        else:
            a = self.nums.pop(0)
            b = self.nums.pop(0)
            c = self.nums.pop(0)
            self.root = TreeNode(a)
            if b is not None:
                self.root.left = TreeNode(b)
            else:
                self.root.left = b
            if c is not None:
                self.root.right = TreeNode(c)
            else:
                self.root.right = c
            self.queue.append(self.root.left)
            self.queue.append(self.root.right)
 
    def main(self):
        while len(self.nums) > 0 and len(self.queue)> 0:
            node = self.queue.pop(0)
            if node is not None:
                num= self.nums.pop(0)
                if num is not None:
                    node.left = TreeNode(num)
                else:
                    node.left = num
                if len(self.nums) > 0:
                    num = self.nums.pop(0)
                else:
                    num = None
                if num is not None:
                    node.right = TreeNode(num)
                else:
                    node.right = num
                self.queue.append(node.left)
                self.queue.append(node.right)
        return self.root

二叉树的基础知识：

• 有且仅有一个父节点
• 除了根节点之外，其余节点只有一个父节点
• 每个节点都可以构成以它为根的树
• 每个节点最多有两个孩子，有左右之分
  几个特殊的二叉树：

1. 满二叉树：叶子节点在最下层，除叶子节点外，每个节点度均为2（总节点数：1+2^1+…+2^(k-1)=2^k-1)
2. 完全二叉树：若有度为1的节点，则只可能有一个，并且该节点只有左孩子而无右孩子(是一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树)
3. 二叉排序树（BST，也叫二叉搜索树/查找树）：左子树上所有节点的关键字均小于****根节点的关键字，右子树上的所有节点的关键字均大于****根节点的关键字，左子树和右子树又各是一棵二叉排序树（相对特殊，有排序的概念，对一个二叉排序树做中序遍历可以得到一个递增的有序序列）
4. 平衡二叉树：任意节点的左子树和右子树的深度之差不超过1

二叉搜索树:(Binnary Search Tree)
二叉搜索树与链表的关系(left right parent)

二叉树的插入操作
二叉树的删除操作
二叉树的四种遍历方式要十分的熟悉其中的思路和逻辑，程序模板烂熟于心。属于基础中的基础要掌握的部分，其中的书中的内容也是一样的（按照某条搜索路径访问树中的每个节点）：
掌握的主要解决方式就是自己再重新的做一遍。
递归算法（短小精悍，重在理解）与非递归算法（利用栈队列的思路来解题）

最常见的四种遍历（根节点在何时被访问）：

1. 前序遍历：preorder
2. 中序遍历:inorder
3. 后序遍历:posrorder
4. 层序遍历

三种遍历方式的总结：

• 每个节点都访问一次且仅访问一次，时间复杂度O(n)
• 递归工作栈的栈深为树的深度，空间复杂度为O(n)

构建一个二叉树的类

#当成模板来记忆的
class TreeNode:
    def __init__(self,val):
        self.val=val
        self.left =None
        self.right=None

以下为二叉树的一些主要的题目：要多多的做，多多的总结，并总结出二叉树的一些具体的框架出来（很重要），之所以要多多做，因为这类题目涉及到后面的一些理解，很多时候是前面的基础没有打牢靠，概念没有吃透，这种不像数组那类题目至少是有思路的，这种就是完全没有没有，很多时候就无从下手的感觉，也是因为没有抽象出来的原因……，再做了这么多题目之后，也要总结出一些相应的框架思维出来，即使具体的代码可能不会写，但是大的方向不会错，剩下的就是往里面填充东西。

1. leetcoad144-前序遍历(easy)
2. leetcoad102-层序遍历(middle)
3. leetcoad100-相同的树(easy)
4. leetcoad101-对称二叉树(easy)
5. leetcoad-104二叉树的最大/最小深度
6. leetcoad108-将有序数组转化为二叉搜索树(easy)
7. leetcoad110-平衡二叉树(easy)
8. leetcoad105-从前序与中序遍历构造二叉树(middle)
9. leetcoad235-二叉搜索树的最近公共祖先(middle)
10. leetcoad236-二叉树的最近公共祖先(middle)
11. leetcoad113-路径总和III（middle）
12. leetcoad199-二叉树的右视图（middle）
13. leetcoad114-二叉树展开为链表
14. leetcoad538-把二叉搜索树转换为累加树
15. leetcoad450-删除二叉搜索树中的节点
16. leetcoad297-二叉树的序列化与反序列化
17. leetcoad222-完全二叉树的节点个数
18. leetcoad257二叉树的所有路径
19. leetcoad404-左叶子之和
20. leetcoad513-找树左下角的值
21. leetcoad669-修剪二叉搜索树
22. leetcoad530-二叉搜索树的最小绝对差

三种遍历方式要全部掌握相应的核心递归和迭代写法

leetcoad144-前序遍历:(easy)
若二叉树为空，则什么也不做，否则：

• 访问根节点
  -** 先序遍历左子树**
• 先序遍历右子树

非递归的写法：（需要借助栈和指针来完成）

# 这个版本暂时放在这里，不做处理
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        node,stack,preorderReslut=root,[],[]
        nodeLeft = 100
        nodeRight = 200
        nodeUp = 300
        nodeState = nodeLeft

        # 对二叉树进行遍历
        while node :
            if nodeState == nodeLeft :
                # 在将要访问左孩子地时候加入节点值，形成根--左---右
                preorderReslut.append(node.val)
                if node.left :
                    stack.append(node)
                    node = node.left
                else:
                    nodeState = nodeRight

            elif nodeState == nodeRight:
                if node.right :
                    stack.append(node)
                    node = node.right
                    nodeState = nodeLeft
                else:
                    nodeState = nodeUp
            elif nodeState == nodeUp : 
                parent = None
                if stack :
                    parent = stack.pop()
                    if parent.left == node :
                        nodeState = nodeRight
                node = parent
        return preorderReslut

下面的一些代码是自己经过精心整理的部分，统一了模板的形式（迭代与递归的写法）
非递归的写法：（需要借助栈和指针来完成）
递归实现时，是函数自己调用自己，一层层的嵌套下去，操作系统/虚拟机自动帮我们用栈来保存了每个调用的函数，现在我们需要自己模拟这样的调用过程

前序遍历
利用栈先进后出的原则，先将右子树入栈，再将左子树入栈，下面的流程图很好的解释了根–左–右的过程（打印的过程）

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        # 一开始就将头节点加入栈中
        stack,res=[root],[]
        while stack:
            node=stack.pop()
            # 将根节点的值加入到结果中(打印) 
            res.append(node.val) 
            # 右子树入栈
            if node.right:
                stack.append(node.right)
            # 左子树入栈
            if node.left:
                stack.append(node.left)
        return res

为了与下面中序和后序的模板对应，有了第二种写法，与上面的解法有点不同

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        cur,stack,res=root,[],[]
        # 利用的是两层循环
        while cur or stack:
            while cur:  
                #根节点和左孩子入栈，不断地往左子树的方向走，直至cur为空 
                res.append(cur.val)
                stack.append(cur)
                cur=cur.left
            # 每弹出一个元素就达到右孩子，又执行上面的操作
            temp=stack.pop()  
            cur=temp.right
        return res

中序遍历
不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程

# 与前序遍历的模板相同，只是节点temp加入的时机不同
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        cur,stack,res=root,[],[]
        while cur or stack:
            while cur: 
                #cur入栈，并达到最左端的叶子节点，模拟递归的调用  
                stack.append(cur)
                cur=cur.left
            # 当前节点为空了，说明左边走到尽头了，从栈中弹出节点并保存
            temp=stack.pop()
             # 出栈时再加入结果（**）
            res.append(temp.val) 
            # 转向右边的节点，继续上面的整个过程
            cur=temp.right
        return res

后序遍历

# 与前序遍历的代码几乎相同，这里是不断地往右子树方向走，为空后再不断地往左子树方向走
# 最后输出的时候要注意翻转
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        cur,stack,res=root,[],[]
        while cur or stack:
            while cur: 
                # 先到达最右端
                res.append(cur.val)
                stack.append(cur)
                cur=cur.right
            temp=stack.pop()
            cur=temp.left
        # 将最终的数组翻转输出
        return res[::-1]  

采用递归的方式：当成模板记忆就行,只是换了三行代码的顺序
递归的写法是巧妙地利用了系统栈，而迭代写法就是用stack来模拟系统栈
前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root):
            if not root:        
                return 
            res.append(root.val)   #访问根节点
            dfs(root.left)      #递归遍历左子树
            dfs(root.right)   #递归遍历右子树
        dfs(root)
        return res

中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root):
            if not root:        
                return 
            dfs(root.left)      #递归遍历左子树
            res.append(root.val)   #访问根节点
            dfs(root.right)   #递归遍历右子树
        dfs(root)
        return res

后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root):
            if not root:        
                return 
            dfs(root.left)      #递归遍历左子树
            dfs(root.right)   #递归遍历右子树
            res.append(root.val)   #访问根节点
        dfs(root)
        return res

leetcoad102-层序遍历(middle)
leetcoad链接：
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
视频链接：https://www.algomooc.com/795.html

方法不止一种，可以用迭代，也可以用递归的方式来完成，也可以从总结前 中 后序的遍历过程中知道
注意的几个地方：
需要创建用辅助的数组构成的队列来完成
循环的出口，当队列为空的时候，此时遍历就去全部完成

# 迭代写法：本质是一种广度优先搜索
class Solution:
   def levelOrder(self, root: TreeNode) -> List[List[int]]:
       #设置res用来保存输出结果
       res =[]
       #边界情况的处理
       if not root:
           return res
       #设置一个队列，用来存储二叉树中的元素
       queue = deque()
       #在队列中添加二叉树的根节点
       queue.append(root)
       #遍历根节点，直到队列为空，说明访问了二叉树中所有的节点
       while queue:
           #用来记录queue的长度，即每层节点的个数
           size = len(queue)
           #用来保存每一层节点，保存成功后添加到res中
           temp = []
           #使用for循环，将queue中元素添加到temp中
           for _ in range(0,size):
               #从queue中取出一个节点
               node = queue.popleft()
               #把节点存放到temp中
               temp.append(node.val)
               #判断当前节点的左子节点是否有值，如果有，就添加到queue中
               if node.left !=None:
                   queue.append(node.left)
               if node.right !=None:
                   queue.append(node.right)
           res.append(temp)
       return res

leetcoad100-相同的树(easy)
leetcoad链接：https://leetcode-cn.com/problems/same-tree/
解题思路如下：（深度优先搜索-从概念进行入手的）

1. 如果两个二叉树都为空，则两个二叉树相同
2. 如果两个二叉树有且只有一个为空，则两个二叉树一定不相同
3. 如果两个二叉树都不为空
   1. 判断根节点的值是否相同
      * 若不同，二叉树一定不同
      * 若相同再判断
      - 判断两个二叉树的左子树是否相同以及右子树是否相同
      采用深度优先搜索的方法：

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        #如果两个二叉树都为空，则两个二叉树相同
        #if not p and not q:
        if p ==None and q == None:
            return True
        #如果两个二叉树有且只有一个为空，则两个二叉树一定不相同
        #elif not p or not q:
        elif p== None or q == None:
            return False
        #如果两个二叉树都不为空
        else:
            #判断根节点的值是否相同
            if p.val != q.val:
                #如果根节点不同，那么二叉树一定不同
                return False
            #判断两个二叉树的左子树是否相同以及右子树是否相同
            else:
                return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

时间复杂度：O(mim(m,n)),m和n为两个二叉树的节点数，只有当两个二叉树中对应的节点都不为空时才会访问到该节点，因此访问到的节点数不会超过较小的二叉树的节点树。
空间复杂度：O(min(m,n))
从这道题中衍生出来的一些知识点的问题（耐心细致的整理）
leetcoad101-对称二叉树(easy)
leetcoad链接：https://leetcode-cn.com/problems/symmetric-tree/
采用递归的方式来写：
在尝试判断左树与右数对称的条件时，发现跟两树的孩子的对称情况是有关联的
直接写：
def 函数A(左树，右树)：左树节点值等于右树节点值且函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真才返回真

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        #如果两个二叉树都为空，则两个二叉树一定为对称二叉树
        if not root:
            return True
        def search(left,right):
            #递归的终止条件是两个节点都为空
            #或者两个节点中有一个为空
            #或者两个节点的值不相等
            if not left and not right :
                return True
            elif not left or not right :
                return False
            else:
                if left.val!=right.val:
                    return False
                else:
                    return search(left.left,right.right) and search(left.right,right.left)
        return search(root.left,root.right)

采用迭代的方式来写：
略

leetcoad-104二叉树的最大/最小深度
二叉树的深度：根节点到最远叶子节点的最长路径上的节点数
辅助于理解递归的思路，其实是用的深度优先搜索（DFS+分治）

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        #如果root为空，直接返回0
        if not root:
            return 0
        #递归调用 maxDepth,求出当前节点的左子树的最大深度
        left = self.maxDepth(root.left)

        #递归调用 maxDepth,求出当前节点的右子树的最大深度
        right = self.maxDepth(root.right)

        #求出当前节点的左右子树较大的值
        childMaxDepth = max(left,right)

        #二叉树的最大深度就是它的左右子树较大的值加上1
        return childMaxDepth +1

代码可以更加的简化（建立于充分理解的基础上）：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

时间复杂度：O(n)
空间复杂度：O(h) h表示二叉树的高度，递归函数需要栈空间，而栈空间取决于递归的深度
采用迭代的方式来写（广度优先搜索）：
略
参考链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/comments/派大星星

leetcoad108-将有序数组转化为二叉搜索树(easy)
leetcoad链接：
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
视频链接：<>
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
这里有几个点需要注意的：

1. 高度平衡二叉树
2. 二叉搜索树
3. 我反正没有做过，所以是一摸瞎的感觉，但是对于基础不是很好的我，还是很难的，所以相关的一些基础的知识必须在做题的时候认真的补充起来！！！！

看几篇题解的知识，一边整理一边学习：
二叉搜索树中的中序遍历是升序遍历，题目中由于是升序排列的有序数组，那么必然就是二叉搜索树中的中序遍历序列。（也算是一种分析题目吧）
给定的二叉搜索树的中序遍历，能否唯一的确定二叉搜索树？不能，题目中还有一个附加的条件：要满足一个高度平衡的二叉树，如果忽略这个条件，任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树是有多个的

如果增加要求二叉搜索树高度平衡之后，仍然不能唯一的确定二叉搜索树

通过上面的分析我们可以得出：可以选择中间数字作为二叉搜索树的根节点，这样左右两边的数字的个数只相差1，确定平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树，因此可以通过递归的方式创建平衡二叉搜索树。因此本题的本质在于：高度平衡的理解。

解题步骤：

1. 先去找排序数组中中间的那个元素：设置两个索引，分别指向开头位置和结束位置
2. 利用二叉搜索树递归的特性

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.toBST(nums,0,len(nums)-1)
    # 需要另外写一个函数 toBST
    def toBST(self,nums,begin,end):
        if begin >end:
            return None
        # 获取begin到end排序数组的中间元素的下标
        mid=(begin+end)//2
        # 获取以mid为下标的元素，并把这个元素作为转换后的二叉树的根节点

        root=TreeNode(nums[mid])
        # 递归的将mid左侧的所有元素转换为平衡二叉树

        left=self.toBST(nums,begin,mid-1)
        # 递归的将mid右侧的所有元素转换为平衡二叉树
        right=self.toBST(nums,mid+1,end)
        
        # 将mid左侧的所有元素转换为平衡二叉排序树后作为root的左子树
        root.left=left
        # 将mid右侧的所有元素转换为平衡二叉排序树后作为root的左子树
        root.right=right
        # 返回转换好的平衡二叉树
        return root

leetcoad110-平衡二叉树(easy)
leetcoad链接：https://leetcode-cn.com/problems/balanced-binary-tree/
视频链接：<>
思路：应该是有很多种解法的，这里采用自底向上的方式
有一个重要的概念：只有某子树不平衡，那么该树就一定不平衡

1. 要想判断是否是高度平衡的二叉树，先看左子树是不是高度平衡的，再看右子树是不是高度平衡的二叉树
2. 如果是的话，就算左右子树的高度差是否超过1，如果超过1的话就不是一个平衡二叉树
3. 有不符合的情况可以提前返回（在代码中有好几处是可以直接返回不满足的结果的，相当于存在一个剪枝的过程）

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 此时如果根节点的左右深度之差的返回值不为-1，就是平衡二叉树（True）
        return self.recur(root)!=-1
    # 自己写一个私有函数,需要不断的递归调用这个函数
    def recur(self,curNode):
        # 递归的终止条件
        # 如果当前的节点为空，那么高度就是0(当访问的左右子节点为叶子节点的时候)
        if curNode==None:
            return 0

        # 递归的计算当前节点的左子树的高度
        left = self.recur(curNode.left)
        # 如果发现为-1，即3表示左子树中出现了高度差大于2的情况，已经不是平衡二叉树，直接返回这个结果给上层
        # 提前终止后续的判断,全树不平衡
        if left==-1:
            return -1

        # 左子树是平衡二叉树
        # 递归的计算当前节点的右子树的高度
        right=self.recur(curNode.right)
        # 如果发现为-1，即3表示右子树中出现了高度差大于2的情况，已经不是平衡二叉树，直接返回这个结果给上层
        # 提前终止后续的判断
        if right==-1:
            return -1
        
        # 左右子树都是平衡二叉树
        # 计算当前左指数与右子树的高度差值
        # 如果发现小于2，那么返回以当前节点为根节点的子树的最大高度
        if abs(left-right)<2:
            return max(left,right)+1
        else:
            return -1

看了吴师兄的写法，大体上还是不太好想，不过具体的思路还是不错的，是值得自己借鉴和学习的，也许是因为还没有理解到精髓，所以自己再多看几篇题解之后多多总结一下。
这里再次结合K神的题解一起来理解这道题吧，再难也要把这类题目给合理的啃下来呀。
递归返回值：

1. 当节点root的左/右子树的高度差小于2,返回以节点root为根节点的子树的最大高度

（max(left,right）+1）
2. 当节点root的左/右子树的高度差大于等于2，可以提前剪枝，返回-1，代表不是平衡二叉树

递归终止条件：

1. 当越过叶子节点时，返回高度0
2. 当左（右）子树高度 left== -1 时，代表此子树的 左（右）子树 不是平衡树，因此直接返回 −1 ；
   下面采用的是自顶向下的方法，但是存在重复的部分（类似一种暴力的解法）
   本质上需要定义一个计算节点高度的函数
   如果p 是非空节点​：height(p)=max(height(p.left),height(p.right))+1​
   如果p是空节点：height(p)=0
   类似于二叉树的前序遍历：对于当前遍历到的节点，先计算左右子树的高度，如果左右子树的高度差不超过1，再分别递归遍历左右子节点，并判断左子树和右子树是否平衡。是一个自顶向下的递归过程

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return abs(self.height(root.right)-self.height(roo.left)) <2 and self.isBalanced(root.left) and self.isBalanced(root,right)
    # 求二叉树高度的函数（重要的四句代码）
    def height(self,node):
        if not node:
            return 0
        left=self.height(node.left)
        right=self.height(node.right)
        return max(left,right)+1
        # return 1+max(self.height(node.right),self.height(node.left))

leetcoad105-从前序与中序遍历构造二叉树(middle)
leetcoad链接：
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

1. 任意二叉树的前序遍历序列中的第一个元素一定是二叉树的根节点
2. 在中序遍历中，根节点将序列分成两个子序列，如果该元素在根的左边，该元素就是根的左孩子，否则就是右孩子。（序列的排布规则：先是全部的左子节点，然后是根节点，然后是全部的右子节点）
3. 在先序序列中，左子序列的第一个节点是左子树的根节点，右子序列的第一个节点是右子树的根节点。（序列的排布规则：先是一个根节点，然后是全部的左节点，接着是全部的右节点）如此递归下去，唯一的确定这颗二叉树
4. 其实推广开来：都是由遍历序列构造二叉树：
   1. 前序和中序可以唯一确定一颗二叉树
   2. 中序和后续也可以唯一确定一棵二叉树
   3. 层序和中序也可以唯一确定一颗二叉树
5. 本质就是一次深度优先遍历的过程
   

迭代写法：
具体步骤如下：

1. 根据中序遍历，建立索引与中序值的哈希表的关系
2. 根据前序遍历确定根节点，然后继续遍历其他元素思考应该放在哪里，执行一个插入函数
3. 插入函数的撰写：
   1. 如果待插入的节点值等于根节点值，说明已经插入完毕，可以用while循环来写这个插入的过程
   2. 如果通过哈希表获取的节点值的位置小于根节点获取的位置（说明一定是根的左子节点，按照中序遍历的过程，序列的索引大小一定是左<根<右）,这里还要判断一下以root为根的左孩子是否有值， 如果有值就需要插入到左孩子节点的孩子节点上

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        #题目中preorder和inorder中没有重复的元素
        #通过哈希表把中序遍历序列中的值和顺序建立映射关系
        n =  len(inorder)
        map = dict()

        #通过for循环，遍历完中序遍历序列中的所有元素
        for i in range(n):
            #以中序序列中的元素值inorder[i]作为key,以位置i作为value,存放到哈希表中
            map[inorder[i]] = i
        
        #开始构建二叉树
        #把前序遍历序列中的第一个元素preorder[0]，作为二叉树的根节点
        #任意二叉树的前序遍历序列中的第一个元素，一定是二叉树的根节点
        root = TreeNode(preorder[0])

        #继续遍历前序遍历序列中的其他元素
        m = len(preorder)
        for i in range(1,m):
            #先把当前遍历的元素构造为一个二叉树的节点
            node = TreeNode(preorder[i])

            #把构造的节点插入到以root为根节点的二叉树中
            self.insertNode(root,node,map)
        return root

    def insertNode(self,root:TreeNode,node :TreeNode,map :dict):
        #当root和node指向的节点相同的时候，跳出循环
        while root != node :
            #如果node的中序遍历序列位置小于root的中序遍历序列位置
            #说明node应该在root的左子树中
            if map[node.val] < map[root.val]:
                #如果此时root没有左子树
                if not root.left:
                    #将node设置为root的左子树
                    root.left = node
                #如果之前root已经有了左子树，不能直接把root插入到root的左子树上
                #需要判断应该把node插入到root左子树上的孩子节点的那个位置
                root = root.left
            else:
                #如果node的中序遍历序列位置大于root的中序遍历序列位置
                #说明node应该在root的右子树

                #如果此时root没有右子树
                if not root.right:
                    #直接就把node设置为root的右子树
                    root.right = node
                root = root.right

递归写法：
总体上是采用了分治的思想：

1. 前序遍历数组的第 1个数（索引为 0）的数一定是二叉树的根结点
2. 在中序遍历中找这个根结点的索引;
3. 把前序遍历数组”和“中序遍历数组”分为两个部分，分别对应二叉树的左子树和右子树，分别递归完成
4. 总结一下就是：前序找根，中序来分，每次通过前序找到根节点，再用中序遍历确定新的左右子树的范围，最后递归这个过程。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not (preorder and inorder):
            return None
        # 根据前序序列的第一个元素确定根节点
        root=TreeNode(preorder[0])

        # 用preorder[0]去查找中序数组中对应的元素
        mid_index = inorder.index(preorder[0])

        # 递归的处理前序数组的的左边部分和中序数组的左边部分
        root.left=self.buildTree(preorder[1:mid_index+1],inorder[:mid_index])
        
        # 递归的处理前序数组的右边部分和中序数组的右边部分
        root.right=self.buildTree(preorder[mid_index+1:],inorder[mid_index+1:])

        # 返回root节点
        return root

** leetcoad106-从中序和后序遍历中构造二叉树**（middle）
思路和上一题十分的相似：后序遍历数组的最后一个元素即代表根节点，可以利用已知的更节点信息在中序遍历的数组中找到根节点所在的下标，然后根据中序遍历的数组分成左右两部分：左部分是左子树，右部分是右子树，针对每个部分采用同样的方法递归下去构造。
迭代法：
具体思路见：
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/

1. 如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子。
2. 如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子。
   代码后期补上：

leetcoad235-二叉搜索树的最近公共祖先(middle)
leetcoad链接：
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
常规的思路：

1. 先找p的各个祖先的节点
2. 再找q的各个祖先的节点
3. 比较找到的祖先的值，其中的最深的节点就是最近的祖先
   参照吴师兄算法的思路：
4. 充分利用了二叉树的性质：左子节点一定小于父节点，右子节点一定大于父节点
5. 根据公共祖先的定义：最小公共祖先将p和q化为两部分，位于二叉树的两侧

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        #由于所有节点的值都是唯一的，当出现（root.val-p.val)*(root.val-q.val)=0时
        #说明p、q中有一个节点是root节点（p或者q有一个是祖先节点）
        while (root.val -p.val) * (root.val-q.val)>0:
            #当进入到循环中的时候，说明p、q在root的同侧
            #如果p.val<root.val 也说明q.val <root.val
            if p.val < root.val:
                #接下来在左子树中进行查找
                root = root.left
            #如果p.val>root.val 也说明q.val >root.val
            else:
                root = root.right
        #跳出循环，说明（root.val-p.val)*(root.val-q.val)<=0
        #此时root就是p、q的最近的公共祖先
        return root

同样是利用二叉树的性质：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        while root:
            if p.val == root.val:
                return root
            elif q.val == root.val:
                return root
            elif root.val >p.val and root.val <q.val:
                return root
            elif root.val <p.val and root.val >q.val:
                return root
            elif root.val <p.val and root.val <q.val:
                root = root.right
            else:
                root = root.left

简化版本：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        while root:
            if p.val == root.val:
                return root
            elif q.val == root.val:
                return root
            elif (root.val >p.val and root.val <q.val) or (root.val <p.val and root.val >q.val):
                return root
            elif root.val <p.val and root.val <q.val:
                root = root.right
            else:
                root = root.left

简化：elif (root.val >p.val and root.val <q.val) or (root.val <p.val and root.val >q.val):这一行的代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        while root:
            if p.val == root.val:
                return root
            elif q.val == root.val:
                return root
            elif root.val <q.val or root.val <p.val:
                return root
            elif root.val <p.val and root.val <q.val:
                root = root.right
            else:
                root = root.left
        ```
将elif做最后的简化，因为有多种情况是返回的root这个结果，将条件进行合并
```python
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': 
        while root:
            if root.val <p.val and root.val <q.val:
                root = root.right
            elif root.val >p.val and root.val >q.val:
                root = root.left
            else:
                return root

此处也可将root = root.right换一种写法

leetcoad236-二叉树的最近公共祖先(middle)
这道题是当时吴师兄直播的时候的一道重点的题目，也是很有水平的一道题目

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        #1.如果此时访问的节点root为空，那么直接返回空
        if not root:
            return None
        #2.如果此时访问的节点root为指定节点p，那么返回p这个节点
        if root == p:
            return p
        #3.如果此时访问的节点root为指定节点q，那么返回q这个节点
        if root ==q:
            return q
        
        #4.经过1 2 3的判断，root这个节点必然不是p q None这三种情况的节点

        #5.递归去查root的左子树，判断是否包含p q这两个指定节点
        left = self.lowestCommonAncestor(root.left, p,q)

        #6.递归去查root的右子树，判断是否包含p q这两个指定节点
        right = self.lowestCommonAncestor(root.right, p,q)

        #7.判断完root节点，root的左子树以及root的右子树，然后开始向父节点传递信息

        #8.如果root节点的左子树left和右子树right都没有找到指定节点，
        #root本身也不是指定节点，
        #那父节点传递的信息就是以root为根节点的那颗二叉树没有指定节点p和q
        if not left and not right:
            #告诉root的父节点，这里没有找到指定节点 p q
            return None
        
        #9.如果在root节点的左子树left中没有找到指定节点p q
        if not left:
            #返回right，告诉root的父节点，能不能找到指定节点p q，完全取决于right
            return right

        #10.如果在root节点的右子树riight中没有找到指定节点p q
        if not right:
            return left
        #11.此时left不为空，right也不为空
        #此时以root节点为根节点的那颗二叉树中找找到了指定节点p ,也找到了指定节点q
        #此时就告诉父节点，root就是p q的最近公共祖先
        else:
            return root

leetcoad113-路径总和III（middle）
leetcoad链接：https://leetcode-cn.com/problems/path-sum-ii/
视频链接：https://www.algomooc.com/811.html
要点：

1. 用一个栈来保存从叶子节点到根节点的路径
2. 设置一个二维数组来保存满足条件的路径
3. 定义一个value值，记录栈中所有节点值的总和（找到的符合条件的那个路径）

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        #构建一个value，用来计算当前路径下节点的总和
        value= 0
        #构建一个path，用来记录满足条件的路径
        path = []
        #构建一个栈，用来保存当前路径下的节点
        stack =[]
        #从根节点开始搜索所有的节点
        self.search(root,value,targetSum,stack,path)
        #返回满足条件的路径
        return path

    #node为正在遍历的节点
    #value为栈中各个节点的总和
    #targetSum为目标路径的和
    #stack为存储在该路径上的所有节点
    #path存储满足条件，即路径上各个节点之和为 targetSum的那些路径
    def search(self,node:TreeNode,value: int,targetSum: int,stack:[],path: []):
        #如果节点为空，那么就不需要再访问下去了
        if not node:
            return 
        #将当前访问节点的值累加到value上去
        value += node.val
        #把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
        stack.append(node.val)
        #如果访问的节点是叶子节点（当前节点的左子树和右子树均为空）,并且当前路径下的节点之和value与目标值targetSum相等
        #说明找到了一条符合条件的路径的路
        if not node.left and not node.right and value == targetSum:
        #if node.left==0 and node.right ==0 and value == targetSum:
            #把这条路径添加到path中去
            path.append(list(stack))
        #继续递归的搜索当前节点node的左子树
        self.search(node.left,value,targetSum,stack,path)

        #继续递归的搜索当前节点node的右子树
        self.search(node.right,value,targetSum,stack,path)

        #搜索完当前节点的左右子树之后，当前节点已经完成了访问，需要返回到它的父节点
        #value值减去当前节点的值
        value -=node.val

        #栈弹出当前的节点值
        stack.pop()

leetcoad199-二叉树的右视图（middle）
课程链接：https://www.algomooc.com/817.html
leetcoad链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/
设置一个数组用来存储二叉树的右视图
借助队列来保存二叉树的每一层节点

1. 第一层的节点是为1
2. 弹出该节点
3. 如果有左右子树，按照左右子树依次加入到队列当中
4. 判断弹出的值是否能加入到结果数组中
5. 队列的队首元素弹出

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]: 
        #设置一个数组用来储存二叉树的右视图结果
        arr =[]
        #设置一个队列，用来保存二叉树每一层的节点
        queue=deque()
        #边界的判断
        if not root:
            return arr
        #首先，把二叉树的根节点加入到队列中
        queue.append(root)
        #观察队列是否为空
        while queue:
            #1、获取队列的长度(代表二叉树中每一层的节点总数)
            levelSize = len(queue)
            #2、通过一个循环，获取队列中每个节点的左右子树，把这些左右子树节点添加到队列中
            for i in range(levelSize):
                #3、弹出队列的队首元素
                node = queue.popleft()
                #4、判断弹出的节点是否有左子树
                if node.left:
                    #如果有左子树，把它加入到队列中
                    queue.append(node.left)

                #5、判断弹出的节点是否有右子树
                if node.right:
                    #如果有右子树，把它加入到队列中
                    queue.append(node.right)
                
                #对于每一层的二叉树的节点，我们是从左到右依次添加的，所以末尾的节点顺序是levelSize-1
                #6、这个末尾的节点就是这一层中最右侧的节点
                if i==levelSize - 1:
                    #把最右侧的节点值加入到结果中
                    arr.append(node.val)
        return arr

leetcoad114-二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
* 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
* 展开后的单链表应该与二叉树 先序遍历 顺序相同

自己感受：有点难!!!看看就行了，估计现在也弄不懂，不要浪费太多的时间，里面的思想还是得弄懂的。
需要注意的点有以下的几个地方：

1. 目的是要展开为单链表(仍然是一个树的结构，只是模拟成了单链表的结构)
2. 右子指针指向下一个节点，左子指针指向为空
3. 展开的顺序与先序遍历相同（那先序遍历的概念以及代码自然要十分的熟悉）
4. 而且这类的转换应该挺有意义的，可以深刻的理解链表与二叉树之间的关系（本来自己之前就有过想一次性弄懂的想法）
   几个规定：
5. left 为当前节点 node 的左子树
6. right 为当前节点 node 的右子树
7. leftTail 指向当前节点左子树 left 转换为链表之后的尾节点，一开始默认为 None
8. rightTail 指向当前节点右子树 right 转换为链表之后的尾节点，一开始默认为 None
9. tail 指向以当前节点 node 为根节点转换为链表之后的尾节点，一开始默认为 None

简单的几个过程：

1. 首先找到根节点1
2. 找到1的左子树的右节点：4
3. 将5接到4的right节点上
4. 将1的right指向2
5. 将1的left指向None
6. 遍历节点2重复上面的过程
7. 不停的遍历下去，直到遍历到最后的节点6，便可以拉直二叉树

思考的步骤如下：

具体的实施步骤有点细致

1. 设置几个指针：left、right 、leftTail 、rightTali 、tail，把左子树和右子树都转换为单链表的形式
2. 先将 node 的左子树指针置空
3. 如果当前节点存在左子树的时候，那么把左子树转换为链表的形式
   1. 通过 backtrack 函数递归的把当前节点的左子树转换为链表
   2. 用left.Tail指向左子树的最后一个节点（左子树left转换为链表的形式）
   3. 将当前节点的node的right指针指向left（完成当前节点和左子树链表的拼接）
   4. Tail指向左子树的最后一个节点（图解的过程就很清晰）
4. 如果当前节点存在右子树的时候，那么把右子树转换为链表的形式
   1. 通过 backtrack 函数递归的把当前节点的右子树转换为链表
   2. 用right.Tail指向右子树的最后一个节点（右子树right转换为链表的形式）
   3. 把left链表和right链表串联起来（左子树存在的情况下，连接左右子树的链表）
   4. Tail指向右子树的最后一个节点
5. 返回链表的尾节点继续去拼接其他的递归链表

把上面的步骤浓缩一下就是：（是一种原地修改的方式，不断地按照右子树地顺序去遍历给定的二叉树）

1. 将左子树插到右子树的地方（一遇到左子树就插入到节点与右子树之间）
2. 将原来的右子树接到左子树的最右边节点(需要找到左子树最右边的节点，方便右子树拼接过来)
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为None
   相关代码：

class Solution:
    def flatten(self, root: TreeNode) -> None: 
        self.backtrack(root) 
    
    # 传入二叉树的节点，把它转换为链表的形式，返回二叉树的尾节点
    def backtrack(self, node: TreeNode) -> TreeNode : 
        # 1、如果 node 为空，返回 None
        if not node:
            return None
        # 2、如果 node 为叶子节点，返回 node
        if not node.left and not node.right:
            return node
        
        # 下面开始设置几个指针
        # 3、left 为当前节点 node 的左子树
        left=node.left
        # 4、right 为当前节点 node 的右子树
        right=node.right
        # 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点，一开始默认为 None
        leftTail=None
        # 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点，一开始默认为 None
        rightTail=None
        # 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点，一开始默认为 None
        tail=None
        # 8、先将 node 的左子树指针置空
        # 将 node 的左子树转换为链表之后，node 的右指针指向那个链表
        node.left=None

        # 9、如果当前节点存在左子树的时候，那么把左子树转换为链表的形式
        if left!=None:
            # 通过 backtrack 函数递归的把当前节点的左子树转换为链表
            # backtrack 函数指向完之后，left 已经是链表
            # 根据第 5 点的代码，leftTail 指向左子树最后一个节点
            leftTail=self.backtrack(left)

            # 此时，node 的左子树 left 已经是链表的形式
            # 那么将当前节点 node 的 right 指针指向 left，完成了当前节点和左子树链表的拼接
            node.right=left
            # 根据第 7 ，tail 指向左子树最后一个节点
            tail=leftTail
        # 10、如果当前节点存在右子树的时候，那么把右子树转换为链表的形式
        if right!=None:
            # 通过 backtrack 函数递归的把当前节点的右子树转换为链表
            # backtrack 函数指向完之后，right 已经是链表
            # 根据第 6 点的代码，rightTail 指向右子树最后一个节点
            rightTail=self.backtrack(right) 

            # 此时，node 的右子树 right 已经是链表的形式
            # 如果当前节点 node 不存在左子树，那么 node.left = None
            # 由于 node 的右指针就是 right，所以不需要执行其它操作
            # 但如果存在左子树，就需要把 left 链表和 right 链表串联起来
            # 也就是把 left 链表的尾节点和 right 的头节点拼接起来
            if left!=None:
                # 将 leftTail 和 right 转换成的链表链接起来
                leftTail.right=right
            # 如果存在右子树，那么根据第 7 点的代码，tail 指向右子树最后一个节点
            tail=rightTail
        return tail

leetcoad538-把二叉搜索树转换为累加树（middle）

题目描述：
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
* 节点的左子树仅包含键 小于节点键的节点。
* 节点的右子树仅包含键 大于节点键的节点。
* 左右子树也必须是二叉搜索树。

题目中需要注意的点：

1. 本身是一个二叉搜索树（需要弄懂二叉搜索树的定义:也即题目中关于二叉搜索树的约束条件）
2. 转换为累加树（累加树的定义）
3. 有一个不好理解的地方：每个节点node的新值等于原树中大于或等于node.val的值之和(看了一遍题目仍然不能够好好的理解清楚)

leetcoad450-删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的** key 对应的节点，并保证二叉搜索树的性质不变**。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
* 首先找到需要删除的节点；
* 如果找到了，删除它。

题目中需要注意的点如下：

1. 首先还是一个以二叉搜索树为原型的题目
2. 需要从二叉树中删除一个key值并且要保证二叉树的性质不变（首先就得熟悉性质）
3. 熟悉删除节点的步骤（虽然题目给了）
4. 正确的解不止一个

如何删除图中的元素2：

1. 以该节点作为根节点的右子树中最小的那个值
   1. 不断地在右子树中去寻找它地左子树（是一个二叉搜索树，左子树是最小的，越往左的数是越小的，直到找到叶子节点为止）
   2. 3为找的，以2为根节点的右子树中最小的那个值
   3. 用3把该2覆盖，删除以前的3值
   4. 返回二叉搜索树的根节点

归纳总结：

1. 如果 root 为空，那么直接返回空
2. 如果root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
   1. 情况一：当前节点的左子树为空，那么当前节点 root 由** root 的右子树占位**就行
   2. 情况二：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
   3. 情况 三：被删除节点既有左子树，又有右子树
      1. 需要找到右子树最小的值，或者左子树中最大的值（任选一种）
      2. 删除掉 root 的右子树最小的值
3. 如果root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找（可以采用第二种情况的方式删除）
4. 如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找（可以采用第二种情况的方式删除）

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        # 1、如果 root 为空，那么直接返回空
        if not root :
          return None

        # 2、如果 root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
        if root.val == key :

            # 情况 1：当前节点的左子树为空，那么当前节点 root 由 root 的右子树占位就行
            if not root.left:
               return root.right
            # 情况 2：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
            if not root.right :
               return root.left
            # 情况 3：被删除节点既有左子树，又有右子树
            minNodeOfRight =  self.findMinNode(root.right)
            # 找到右子树最小的值之后，修改当前节点 root 的值为右子树最小的值
            root.val = minNodeOfRight.val
            # 同时，记得删除掉 root 的右子树最小的值之
            # 删除操作就是以 root 的右子树作为根节点，key 为右子树最小的值进行删除
            root.right =  self.deleteNode(root.right,minNodeOfRight.val)

          # 3、如果 root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找
        elif root.val < key :
            # 在 root 的右子树中去查找并删除 key 
            root.right =  self.deleteNode(root.right,key)

          # 4、如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找
        elif root.val > key : 
            # 在 root 的左子树中去查找并删除 key 
            root.left = self.deleteNode(root.left,key)

        # 最后返回需要已经删除了 key 的二叉树的根节点
        return root

    # 通过 findMinNode ，可以找到二叉搜索树中最小的元素
    def findMinNode(self , node : TreeNode) -> TreeNode : 

        # 由于二叉搜索树，左子树所有元素的值都小于根节点的值
        # 所以可以不断的查找，直到为叶子节点，那么就找到了
        while node.left :
            # 不断的去查找当前节点的左子树
            node = node.left
        # 返回当前二叉搜索树中最小的元素
        return node

leetcoad297-二叉树的序列化与反序列化

暂时不做

leetcoad222-完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。