本博客的内容只是做一个大概的记录，整个PDF看下来，内容上是不如代码随想录网站上的文章全面的，并且PDF中有些地方的描述，是很让我疑惑的，在困扰我很久后，无意间发现，其网站上的讲解完全符合我的思路。这次看完这些PDF后，暂时一段时间内不会再看了，要复习还是依靠，代码随想录网站，视频，和我自己写的博客吧

二叉树章节

二叉树章节，做不出来的题基本上都有一个共性，对二叉树的数据结构特性不熟悉，从而没有编写思路，或者在判断条件上产生疏漏。

完全二叉树：除了最底层可能没填满，其余每层节点数都达到最大值，并且最下面一层的节点，都集中在该层最左边的若干位置。一个很关键的点：完全二叉树的某些子树，一定是满二叉树，节点数量是可以计算的。去计算最左和最后，一直向左找，计数，一直向右找，计数，如果两数相等，这颗子树就是满二叉树。

二叉搜索树：若它的左子树不空，则左子树上所有节点的值，均小于它的根节点的值。若它的右子树不空，则右子树上所有节点的值，均大于它的根节点的值。它的左右子树也分别为二叉搜索树。

平衡二叉树：它是一个空树，或者它的左右两个子树的高度差的绝对值不超过1，并且左右子树都是一颗平衡二叉树。

二叉树的链式存储，是大家一直在用的，那么其顺序存储，要注意，需要将树填补为一颗满二叉树，才能满足公式，如果父节点的数组下标是 i , 那么它的左孩子就是 i2+1，右孩子是 i2+2 。

在遍历方式上，主要分为两大类，深度优先遍历（前中后序）遍历，广度优先遍历（层序遍历）。层序遍历有时候是很好用的方法，有的题，用递归解法较复杂，或者在代码编写逻辑上不好思考，后面会提到。

深度优先遍历的三种方法中，后序遍历是应用最多的，因为很多时候，我们都需要去收集，左右子树的信息，来决定当前节点的方式，或者说，需要将某些信息，一层一层地返回到根节点，这时候都需要后序遍历。中序遍历，和二叉搜索树，严格绑定。前序遍历需要的场景，一般都有比较明显的特征，可以意识到。

前序遍历：中左右；中序遍历：左中右；后序遍历：左右中。

二叉树的节点定义：

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

递归三部曲

1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑

判断了递归中不会有空节点，就可以不写返回条件？以前序遍历为例

两个版本代码的对比，一个带空节点判断，一个不带。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []
        self.res = []
        self.digui(root)
        return self.res


    def digui(self,root):
        self.res.append(root.val)
        if root.left:
            self.digui(root.left)
        if root.right:
            self.digui(root.right)

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []
        self.res = []
        self.digui(root)
        return self.res


    def digui(self,root):
        if root == None :
            return
        self.res.append(root.val)
       
        self.digui(root.left)
        
        self.digui(root.right)

二叉树的迭代遍历(一定要学会)

前序遍历：

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []
        stack = [root]
        res = []
        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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []

        stack = [root]
        res = []
        while stack :
            node = stack.pop()
            res.append(node.val)
            # 空节点不入栈
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            # 代码编写顺序是，中左右，但是因为使用的是栈，那么在res数组中的顺序是，中右左，倒序，左右中

        return res[::-1]

中序遍历：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []

        stack = []
        cur = root
        res = []
        while stack or cur:
        # 同样注意，空节点不入栈
            if cur :
                stack.append(cur)
                cur = cur.left
            else :
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right

        return res

上面三种迭代方法，需要注意的共同点是：迭代法中，要保证，空节点不入栈。

前中后序遍历的，统一迭代方法

以中序遍历为例：因为是迭代法，使用的是栈作为数据结构，在代码中的编写顺序，和在结果集中的保存顺序，是不一样的。代码编写是，右中左，结果集中就是，左中右

lass Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []

        stack = [root]
        
        res = []
        while stack :
            node = stack.pop()
            if node == None :
                node = stack.pop()
                res.append(node.val)        
            else :
                # 当node不是空节点时的操作，是关键
                # 要根据遍历顺序重新调整元素顺序
                # 因为是使用堆栈，所以要从下向上看，左中右
                if node.right :  # 右
                    stack.append(node.right)
                stack.append(node) # 中
                stack.append(None)
                if node.left : # 左
                    stack.append(node.left)

        return res

二叉树的层序遍历

层序遍历是有标准写法的。代码随想录中列出的，与层序遍历相关的10道题，都是稍微修改就可以做出来的。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None :
            return []
        dq = deque()
        dq.append(root)
        res = []
        level = []
        while dq :
            size = len(dq)
            for i in range(size):
                node = dq.popleft()
                level.append(node.val)
                if node.left :
                    dq.append(node.left)
                if node.right :
                    dq.append(node.right)
            res.append(level)
            level = []
        return res

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

以层序遍历为模板。

from collections import deque
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None :
            return root
        dq = deque()
        dq.append(root)
        pre = None
        while dq :
            size = len(dq)
            for i in range(size):
                if i == 0 :
                    pre = dq.popleft()
                else :
                    node = dq.popleft()
                    pre.next = node
                    pre = node
                if pre.left :
                    dq.append(pre.left)
                if pre.right :
                    dq.append(pre.right)
        return root

104.二叉树的最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        depth = 0
        queue = collections.deque([root])
        
        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return depth

111.二叉树的最小深度

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点.

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        queue = collections.deque([root])
        
        while queue:
            depth += 1 
            for _ in range(len(queue)):
                node = queue.popleft()
                
                if not node.left and not node.right:
                    return depth
            
                if node.left:
                    queue.append(node.left)
                    
                if node.right:
                    queue.append(node.right)

        return depth

上面求最大深度和最小深度的题目，我们后面还会遇到，可以发现，其实递归也不一定比迭代法好用，只不过能不能想的到，使用层序遍历，就是需要修炼的了。

226.翻转二叉树，通过本题，希望学会，如何将递归方法中的逻辑，写在相对应的迭代法中

本题用什么遍历顺序？

对于使用基于递归的方法来说：前序，后序，层序，都可以。唯独中序不行。这个自己画画图就可以知道。

对于使用迭代的方法来说：同递归。（这里的迭代，指的是，不加入None的迭代法）

对于使用统一方式迭代的方法来说：任何顺序都可以。

递归代码，前序遍历：

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None :
            return root
        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 not root:
            return None
        self.invertTree(root.left)
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        return root

迭代代码，中序遍历：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None      
        stack = [root]        
        while stack:
            node = stack.pop()                   
            if node.left:
                stack.append(node.left)
            node.left, node.right = node.right, node.left               
            if node.left:
                stack.append(node.left)       
        return root

迭代代码，前序遍历：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None      
        stack = [root]        
        while stack:
            node = stack.pop()   
            node.left, node.right = node.right, node.left                   
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)  
        return root

统一迭代风格的C++代码，中序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

为什么这个中序就是可以的呢，因为这是用栈来遍历，而不是靠指针来遍历，避免了递归法中翻转了两次的情况。

只要是能编写出相应迭代法的递归法，在时间复杂度上二者差不多，在空间复杂度上，迭代法要优于递归。因为递归需要系统堆栈存储参数，返回值等信息。

通过上一题，我们要意识到，非统一版本的迭代法，前序和后序都是基于栈的，也是靠栈来遍历的，而非统一版本的迭代法的中序遍历，是靠指针来遍历的。这二者是不同的。而统一版本的迭代法，前中后序都是基于栈来遍历的。

对称二叉树

这道题就是后序遍历，但是我觉得在编写风格上，对我来说总感觉这不是后序遍历，用前序遍历的逻辑就写出来了，似乎我还没有完全掌握这道题。
递归法：

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root == None :
            return True
        return self.digui(root.left,root.right)
        

    def digui(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
        else :
            if left.val != right.val :
                return False
            else :
                flag1 = self.digui(left.left,right.right)
                flag2 = self.digui(left.right,right.left)
                return flag1 and flag2

迭代法：没写出来，困惑点在于：在判断时，需要考虑空节点，但是迭代法的空节点，应该不能入栈的？
使用队列：

import collections
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        queue = collections.deque()
        queue.append(root.left) #将左子树头结点加入队列
        queue.append(root.right) #将右子树头结点加入队列
        while queue: #接下来就要判断这这两个树是否相互翻转
            leftNode = queue.popleft()
            rightNode = queue.popleft()
            if not leftNode and not rightNode: #左节点为空、右节点为空，此时说明是对称的
                continue
            
            #左右一个节点不为空，或者都不为空但数值不相同，返回false
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            queue.append(leftNode.left) #加入左节点左孩子
            queue.append(rightNode.right) #加入右节点右孩子
            queue.append(leftNode.right) #加入左节点右孩子
            queue.append(rightNode.left) #加入右节点左孩子
        return True

使用栈：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        st = [] #这里改成了栈
        st.append(root.left)
        st.append(root.right)
        while st:
            rightNode = st.pop()
            leftNode = st.pop()
            if not leftNode and not rightNode:
                continue
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            st.append(leftNode.left)
            st.append(rightNode.right)
            st.append(leftNode.right)
            st.append(rightNode.left)
        return True

层次遍历：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        queue = collections.deque([root.left, root.right])
        
        while queue:
            level_size = len(queue)
            
            if level_size % 2 != 0:
                return False
            
            level_vals = []
            for i in range(level_size):
                node = queue.popleft()
                if node:
                    level_vals.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
                   # 注意层次遍历这里，空节点也要入栈的，这样才能比较
                else:
                    level_vals.append(None)
                    
            if level_vals != level_vals[::-1]:
                return False
            
        return True

经过上一题，学会了如何处理，在迭代法中要处理空节点的情况。统一风格的迭代法中，因为要用空节点来标记要处理的中间节点，就不能再让空节点入栈了。中序迭代遍历也不行，因为中序迭代法，是需要指针来指示当前位置的，所以也要求空节点不入栈。

前序遍历：

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None :
            return []
        stack = [root]
        res = []
        while stack :
            node = stack.pop()
            if node == None :
                continue
            res.append(node.val)

            stack.append(node.right)
 
            stack.append(node.left)
        return res

层序遍历：

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None :
            return []
        dq = deque()
        dq.append(root)
        res = []
        level = []
        while dq :
            size = len(dq)
            for i in range(size):
                node = dq.popleft()
                if node == None :
                    continue
                level.append(node.val)
                
                dq.append(node.left)
                
                dq.append(node.right)
            if level != []:
                res.append(level)
            level = []
        return res

二叉树的最大深度

根节点的高度等于最大深度，后序遍历很好写。求高度，是自底向上的，用后序遍历。求深度，是自顶向下的，用前序遍历。
高度求解法：

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

深度求解法：递归

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        self.maxd = 0
        depth = 0
        self.digui(root,depth)
        return self.maxd

    def digui(self,root,depth):
        if root == None :
            if depth > self.maxd :
                self.maxd = depth
            return

        self.digui(root.left,depth+1)
        self.digui(root.right,depth+1)

迭代法，求深度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        stack = [(root,1)]
        maxd = 0
        while stack :
            (cur,depth) = stack.pop()
            maxd = max(maxd,depth)
            if cur.left :
                stack.append((cur.left,depth+1))
            if cur.right :
                stack.append((cur.right,depth+1))

        return maxd

层序遍历法：
套用模板即可。

统一编写风格的迭代法：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        stack = [(root,1)]
        maxd = 0
        while stack :
            (cur,depth) = stack.pop()
            if cur :
            	# 中
                stack.append((cur,depth))
                stack.append((None,0))
                # 左
                if cur.left :
                    stack.append((cur.left,depth+1))
                # 右
                if cur.right :
                    stack.append((cur.right,depth+1))
                # 那么在栈中的顺序就是：右左中，当然这里什么顺序都不是了，因为不需要回溯，只需要记录每次的depth
            else :
                (cur,depth) = stack.pop()
                maxd = max(maxd,depth)

        return maxd

虽然我们之前写过了，前中后序的迭代法代码，但是并不代表，迭代法的代码和递归中的前中后序对应，非统一编写风格的迭代法只能模拟前序遍历，后序遍历是通过翻转，中序遍历是通过指针。统一编写风格的迭代法，是可以利用栈来模拟递归和回溯的，代码随想录中也说了，有些递归算法的对应迭代法，写起来的代码逻辑是很难的。

非统一编写风格中，因为空节点不入栈，所以无法知道，目前代码的处理逻辑在哪个节点。但是统一风格下，有None的存在，当遍历到叶子节点时，我们可以通过pop四次，得到左右叶子，将处理的结果append进栈，再append一个None，我目前感觉这样的处理逻辑应该可行。

求二叉树的最小深度

后序：

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        # 这里也可以不用left和right来判断，可以用root.left,root.right是否为None来判断
        if left == 0 and right != 0 :
            return 1+right
        elif left != 0 and right == 0 :
            return 1+left
        # 这个判断条件冗余了，和下面else的结果一样
        elif left == 0 and right == 0 :
            return 1
        else :
            return 1 + min(left,right)

有点乱了，求最小深度，前序和迭代，不会写

前序：

class Solution:
    def __init__(self):
        self.result = float('inf')

    def getDepth(self, node, depth):
        if node is None:
            return
        if node.left is None and node.right is None:
            self.result = min(self.result, depth)
        if node.left:
            self.getDepth(node.left, depth + 1)
        if node.right:
            self.getDepth(node.right, depth + 1)

    def minDepth(self, root):
        if root is None:
            return 0
        self.getDepth(root, 1)
        return self.result

迭代：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        depth = 0
        queue = collections.deque([root])
        
        while queue:
            depth += 1 
            for _ in range(len(queue)):
                node = queue.popleft()
                
                if not node.left and not node.right:
                    return depth
            
                if node.left:
                    queue.append(node.left)
                    
                if node.right:
                    queue.append(node.right)

        return depth

完全二叉树的节点个数

利用完全二叉树的性质，提前判断。但归根结底还是后序遍历。

如果是一般二叉树，可以递归可以层序遍历，但是想要利用完全二叉树的性质，只能递归。

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        if root.left == None and root.right == None :
            return 1
        return self.count_fun(root)


    def count_fun(self,root):
        if root == None :
            return 0
        cleft = 0
        cright = 0
        head1 = root
        head2 = root
        while head1.left :
            head1 = head1.left
            cleft += 1
        while head2.right :
            head2 = head2.right
            cright += 1
        if cleft == cright :
            number = pow(2,cleft+1)-1
            return number
        else :
            return 1 + self.count_fun(root.left) + self.count_fun(root.right)

平衡二叉树

一开始是想就用题目给的 isBalanced 函数，一个函数解决问题，但是发现要从叶子节点计算高度，所以还得两个函数。

在一个就是本题，别想着整个在迭代开始前的判断剪枝，其实省不了多少空间，还可能导致返回值异常的bug。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root == None :
            return True

        self.res = True
        self.compute(root)

        return self.res


    def compute(self,root):
        
        if root == None :
            return 0
        left = self.compute(root.left)
        right = self.compute(root.right)
        if abs(left-right) > 1 :             
            self.res = False
        
        return 1 + max(left,right)

求深度需要前序遍历，从上到下去查；求高度需要后序遍历，从下到上去计算。

这道题真正想剪枝，应该引入一个不可能的值，作为判断条件。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root == None :
            return True

        self.res = True
        self.compute(root)

        return self.res


    def compute(self,root):
        
        if root == None :
            return 0
        left = self.compute(root.left)
        if left == -1 :
            return -1
        right = self.compute(root.right)
        if right == -1 :
            return -1
        if abs(left-right) > 1 :             
            self.res = False
            result = -1
        else :
            result = 1 + max(left,right)
        
        return result

本题的迭代法太麻烦，要先搞一个函数，专门计算深度，在搞另一个函数，从前序开始，遍历每一个节点，去判断左右子树，太复杂，本题的迭代法不做学习。

二叉树的所有路径

本题我采用了字符串作为承载路径的数据结构，之前我一直习惯用的是列表，可以放心大胆的 append 和 pop ， 用字符串的话，就要想好需不需要回溯，做隐式回溯的话，处理逻辑应该放在哪里。

本题是前序遍历。

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if root == None :
            return None
        self.res = []

        ss = ''

        self.find_allroad(root,ss)

        return self.res

    def find_allroad(self,root,ss):
        if root == None :
            return 
        if root.left == None and root.right == None :
            ss = ss + str(root.val)
            self.res.append(ss)

        self.find_allroad(root.left,ss + str(root.val) + '->')

        self.find_allroad(root.right,ss + str(root.val) + '->')

本题的迭代法，在编写感觉上，与递归稍有不同，关键点在于搞清楚，增加路径的逻辑应该放在哪里，以及遇到叶子节点的处理逻辑，是否需要加入最后一个节点的数值？迭代法因为在初始化时，要有根节点，所以在加入路径的逻辑上，与迭代法不同，要注意体会。

想不明白的时候，就自己模拟试试。

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if root == None :
            return None
        st = [root]
        path = [str(root.val)]
        res = []
        while st :
            node = st.pop()
            ss = path.pop()
            if node.left == None and node.right == None :
                res.append(ss)
            if node.right :
                st.append(node.right)
                path.append(ss+'->'+str(node.right.val))

            if node.left :
                st.append(node.left)
                path.append(ss+'->'+str(node.left.val))

        return res

迭代法，模拟前中后序就用栈，适合层序遍历就用队列。

左叶子之和

感觉自己写的这个代码，逻辑不是很清晰。但是代码随想录的解答也是这样写的，如果当前是左叶子，就覆盖之前计算的值（这个值其实就是0），但是 if 判断又不能放在递归函数前面，那样会将正确的值覆盖。

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        

        left = self.sumOfLeftLeaves(root.left)
        right = self.sumOfLeftLeaves(root.right)
        if root.left != None and root.left.left == None and root.left.right == None :
            left = root.left.val

        return left + right

错误的 if 位置，错误的代码：

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        
		if root.left != None and root.left.left == None and root.left.right == None :
            left = root.left.val

        left = self.sumOfLeftLeaves(root.left)
        right = self.sumOfLeftLeaves(root.right)
  
        return left + right

迭代法：前序遍历，统计每一个左叶子就好了。

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
       
        st = [root]
        res = 0
        while st :
            node = st.pop()
            if node.left != None and node.left.left == None and node.left.right == None :
                res += node.left.val
            if node.left :
                st.append(node.left)
            if node.right :
                st.append(node.right)

        return res

树左下角的值

本题使用层序遍历，思路非常简单，是层序遍历的模板题，这里我使用递归。

递归，要使用前序遍历，这样才能优先左边搜。

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.maxdepth = 0
        # 如果depth初值给0的话，因为一开始会等于maxdepth，就要单独判断，二叉树只有一个
        # 根节点的情况了，如果给1的话，就不需要单独判断
        depth = 1
        self.value = 0
        self.find_left(root,depth)

        return self.value

    def find_left(self,root,depth):
        if root == None :
            return
        if root.left == None and root.right == None :
            # 本题的关键就在于这一句，必须是严格大于
            if depth > self.maxdepth :
                self.maxdepth = depth
                self.value = root.val

        self.find_left(root.left,depth+1)
        self.find_left(root.right,depth+1)

路径总和

第一次自己尝试编写，代码随想录风格的，利用设置返回值，找到就返回的递归代码。

需要注意的还是那一点：理清处理逻辑，递归函数怎么写，需不需要回溯，需要回溯，想写成隐式的怎么写，显式的怎么写，在收获结果的时候，处理逻辑怎么写，终止条件怎么写。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root == None :
            return False
        # 注意处理逻辑，一开始这里最后一个条件我写的是：targetSum == 0 ，一直错误
        # 后来才发现，我没有去处理最后一个节点！
        if root.left == None and root.right == None and targetSum == root.val :
            return True

        if self.hasPathSum(root.left,targetSum-root.val) :
            return True

        if self.hasPathSum(root.right,targetSum-root.val) :
            return True
        
        return False

迭代法：

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root == None :
            return False
        st = [root]
        value = [targetSum]
        while st :
            node = st.pop()
            t = value.pop()
            if node.left == None and node.right == None and t == node.val :
                return True

            if node.left :
                st.append(node.left)
                value.append(t-node.val)

            if node.right :
                st.append(node.right)
                value.append(t-node.val)

        return False
            

路径总和II

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if root == None :
            return []

        self.res = []
        path = []
        self.find_all_road(root,path,targetSum)

        return self.res

    def find_all_road(self,root,path,targetSum):
        if root == None :
            return
        
        if root.left == None and root.right == None and targetSum == root.val :
            path.append(root.val)
            self.res.append(path.copy())
            path.pop()

        path.append(root.val)
        self.find_all_road(root.left,path,targetSum-root.val)
        self.find_all_road(root.right,path,targetSum-root.val)
        path.pop()

用迭代法记录所有路径是很繁琐的，这种题不适合迭代法，一定要体会其中区别！问“有没有？”，迭代法可以；“找出所有可能？”迭代法不行。

递归函数，什么时候需要返回值，什么时候不需要？

如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）

如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）

如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

前面两道，路径总和的题，可以在子节点判断后，再加一个判断做剪枝

		if root == None :
            return
        
        if root.left == None and root.right == None and targetSum == root.val :
            path.append(root.val)
            self.res.append(path.copy())
            path.pop()
        if root.left == None and root.right == None :
             return

但是一定要注意顺序，要放在判断当前叶子节点不符合要求之后。

前面两题，我写的和代码随想录写的细节有些不同，我是从空列表开始递归，卡哥是先让根节点入栈了，这一个差异，就导致代码编写风格差异一看上去还挺大。

中序后序建立二叉树，前序中序建立二叉树，这两题只要想清楚，区间的左右边界就可以了，过。

最大二叉树，同上一题，都是构造的题目

合并二叉树

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None and root2 == None :
            return None
        elif root1 == None :
            return root2
        elif root2 == None :
            return root1
        else :
            root1.val += root2.val
        
        root1.left = self.mergeTrees(root1.left,root2.left)
        root1.right = self.mergeTrees(root1.right,root2.right)
 
        return root1

构造树，一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

迭代法：代码随想录给的是用对队列，但是并不是层序遍历的模板！用栈作为容器一样可以！这里我是用的栈。

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None :
            return root2
        if root2 == None :
            return root1
        head = root1

        st = [root1,root2]
        while st :
            # 因为用的是栈，后进先出，这里顺序要注意，是反的
            root2 = st.pop()
            root1 = st.pop()
            root1.val += root2.val

            # 在四个有效的判断中，顺序很重要，要先判定左右是否都不空
            # 因为当root有空时，会存在给root1的赋值操作，这时候再判断，本来一空一不空，
            # 现在变成都不空了，出现错误！

            if root1.left != None and root2.left != None :
                st.append(root1.left)
                st.append(root2.left)
            if root1.right != None and root2.right != None :
                st.append(root1.right)
                st.append(root2.right)
       
            if root1.left == None and root2.left != None :
                root1.left = root2.left
            if root1.left != None and root2.left == None : # 可不写
                pass 
            if root1.right == None and root2.right != None :
                root1.right = root2.right
            if root1.right != None and root2.right == None : # 可不写
                pass
           
            # 还有，root1和root2的左孩子均为空，root1和root2的右孩子均为空
            # 这两种情况，也可以不写
 
        return head

二叉搜索树中的搜索

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None :
            return None
        if root.val == val :
            return root
        
        if root.val > val :
            res = self.searchBST(root.left,val)
            if res :
                return res

        else :
            res = self.searchBST(root.right,val)
            if res :
                return res
        return None

精简版本：不管返回值是不是None ， 直接返回就行！

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None :
            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)

二叉搜索树，因为其结构特殊性的存在，不需要回溯操作，所以不需要栈或队列来模拟递归。直接循环！

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root == None :
            return None
        while root != None :

            if root.val == val :
                return root
            if root.val > val :
                root = root.left
            else :
                root = root.right

        return None

验证二叉搜索树(重要！重要！重要！因为我一直不会)

这道题我竟然还是不会！

现在能想到，避开陷阱，不是仅仅比较左右孩子就可以的！

但是，依然忘了迭代法怎么编写！

递归法就是先中序遍历得到数组，再遍历数组。

class Solution:
    def __init__(self):
        self.vec = []

    def traversal(self, root):
        if root is None:
            return
        self.traversal(root.left)
        self.vec.append(root.val)  # 将二叉搜索树转换为有序数组
        self.traversal(root.right)

    def isValidBST(self, root):
        self.vec = []  # 清空数组
        self.traversal(root)
        for i in range(1, len(self.vec)):
            # 注意要小于等于，搜索树里不能有相同元素
            if self.vec[i] <= self.vec[i - 1]:
                return False
        return True

这里用递归法的一个技巧在于，声明一个全局变量节点。

class Solution:
    def __init__(self):
        self.pre = None  # 用来记录前一个节点

    def isValidBST(self, root):
        if root is None:
            return True

        left = self.isValidBST(root.left)

        if self.pre is not None and self.pre.val >= root.val:
            return False
        self.pre = root  # 记录前一个节点

        right = self.isValidBST(root.right)
        return left and right

迭代法：

class Solution:
    def isValidBST(self, root):
        stack = []
        cur = root
        pre = None  # 记录前一个节点
        while cur is not None or len(stack) > 0:
            if cur is not None:
                stack.append(cur)
                cur = cur.left  # 左
            else:
                cur = stack.pop()  # 中
                if pre is not None and cur.val <= pre.val:
                    return False
                pre = cur  # 保存前一个访问的结点
                cur = cur.right  # 右
        return True

看到二叉搜索树就要想到中序遍历，中序遍历得到的数组是递增的。

二叉搜索树的最小绝对差

代码逻辑和上一题完全相同。

class Solution:
    def __init__(self):
        self.pre = None
        self.minabs = inf
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        self.getMinimumDifference(root.left)
        if self.pre != None :
            self.minabs = min(self.minabs,root.val-self.pre.val)

        self.pre = root

        self.getMinimumDifference(root.right)

        return self.minabs

class Solution:
    
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if root == None :
            return 0
        res = inf
        pre = None
        cur = root
        st = []
        while st or cur :
            if cur :
                st.append(cur)
                cur = cur.left
            else :
                cur = st.pop()
                if pre != None :
                    res = min(res,cur.val-pre.val)
                pre = cur
                cur = cur.right

        return res

二叉搜索树中的众数

怎么bug一直调不好了？这题有很多细节我没注意到，下面的是错误的代码

class Solution:
   
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        
        self.maxcount = 1
        self.res = []
        self.pre = None
        self.count = 1
        self.findall(root)
        return self.res

    def findall(self,root):
        if root == None :
            return 

        self.findall(root.left)
        if self.pre :
            if self.pre.val == root.val :
                self.count += 1
            else :
                count = 1

        if self.count > self.maxcount :
            self.res.clear()
            self.res.append(root.val)
            self.maxcount = self.count
        elif self.count == self.maxcount :
            self.res.append(root.val)
            

        self.pre = root
        self.findall(root.right)

上述代码的致命错误，大致如下：首先是初始化上的错误，两个计数器必须全部置0，另外，让根节点进去结果列表，这是毫无道理的！第二点就是没有处理好第一个节点（最左下的节点），当 pre 是 None 时，我们应该将 count 赋值为 1 ，这样最左下的节点就可能作为结果。第三点，对于当前节点是否是空节点的判断，只能决定，当前的 count 是多少，而结果处理逻辑，肯定是要放在 if 判断之外的，不然也同样会漏掉，最左下节点作为结果的情况。

正确代码：

class Solution:
   
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        
        self.maxcount = 0
        self.res = []
        self.pre = None
        self.count = 0
        self.findall(root)
        return self.res

    def findall(self,root):
        if root == None :
            return 

        self.findall(root.left)
        if self.pre :
            if self.pre.val == root.val :
                self.count += 1
            else :
                self.count = 1
        else :
            self.count = 1

        if self.count > self.maxcount :
            self.res.clear()
            self.res.append(root.val)
            self.maxcount = self.count
        elif self.count == self.maxcount :
            self.res.append(root.val)
            

        self.pre = root
        self.findall(root.right)

迭代法，就是中序遍历，只要理清本题的，众数处理逻辑就好，和递归的逻辑是一样的

class Solution:
   
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        
        count = 0
        maxcount = 0
        pre = None
        cur = root
        st = []
        res = []
        while st or cur :
            if cur :
                st.append(cur)
                cur = cur.left
            else :
                cur = st.pop()
                if pre :
                    if pre.val == cur.val :
                        count += 1
                    else :
                        count = 1
                else :
                    count = 1
                pre = cur
                if count > maxcount :
                    res.clear()
                    res.append(cur.val)
                    maxcount = count
                elif count == maxcount :
                    res.append(cur.val)

                cur = cur.right

        return res

如果本题不是二叉搜索树，而是一般二叉树，就要利用字典了

from collections import defaultdict

class Solution:
    def searchBST(self, cur, freq_map):
        if cur is None:
            return
        freq_map[cur.val] += 1  # 统计元素频率
        self.searchBST(cur.left, freq_map)
        self.searchBST(cur.right, freq_map)

    def findMode(self, root):
        freq_map = defaultdict(int)  # key:元素，value:出现频率
        result = []
        if root is None:
            return result
        self.searchBST(root, freq_map)
        max_freq = max(freq_map.values())
        for key, freq in freq_map.items():
            if freq == max_freq:
                result.append(key)
        return result

二叉树的最近公共祖先

首先明确用后序遍历，其次要明白，为什么当左右只有一个有值时，返回这个值就可以了。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        if root == None :
            return None
        if root == p or root == q :
            return root

        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left != None and right != None :
            return root
        elif left != None and right == None :
            return left
        elif left == None and right != None :
            return right
        else :
            return None

本题没有迭代法，本题的讲解写的很好，可以多读读。
最近公共祖先

二叉搜索树的最近公共祖先

又没写出来，错误代码如下。受上一题影响，总想在上一题的基础上稍作改动，但是发现，在二叉搜索树中，同时匹配两个值是不现实的，逻辑会非常混乱。

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

这道题，因为有序树的存在，思路和上一题完全不一样了！本题的核心在于利用二叉搜索树的性质。需要理解的是，按照如下规则找到的节点，一定是最近的公共祖先，因为一旦向下进入左右孩子，必然会丢失掉 p q 中的一个。

class Solution:
    def traversal(self, cur, p, q):
        if cur is None:
            return cur
                                                        # 中
        if cur.val > p.val and cur.val > q.val:           # 左
            left = self.traversal(cur.left, p, q)
            if left is not None:
                return left

        if cur.val < p.val and cur.val < q.val:           # 右
            right = self.traversal(cur.right, p, q)
            if right is not None:
                return right

        return cur

    def lowestCommonAncestor(self, root, p, q):
        return self.traversal(root, p, q)

既然本题已经无所谓遍历顺序，变成了一道寻找二叉搜索树的节点的题目，迭代法自然可行，且简便了。

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

二叉搜索树中的插入操作

本题要注意的是，一定要写递归函数返回值，利用返回值去修改二叉树，如果没有修改，返回值就是原本树的自身。

另外，本题要理解，明确只往空节点插入就可以了，不要想着更改树的结构。

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        root = self.insert(root,val)
        return root


    def insert(self,root,val):
        if root == None :
            node = TreeNode(val)           
            return node

        if root.val > val :
            root.left = self.insert(root.left,val)

        else :
            root.right = self.insert(root.right,val)

        return root

其实不需要额外定义一个函数。

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
       
        if root == None :
            node = TreeNode(val)           
            return node

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

        else :
            root.right = self.insertIntoBST(root.right,val)

        return root

删除二叉搜索树中的节点

这道题写下来还是蛮难的，而且我感觉我现在的逻辑也没有很清晰，加了不少 if 判断。我主要的思路就是，删除当前节点后，直接用当前节点的左孩子顶上来，然后把当前节点的右子树，加到左孩子的最右。这样就满足二叉搜索树的性质。但是还要处理很多特殊情况，这也是我这么多 if 的由来，比如我取了当前节点的左右孩子，那么自然就要考虑，如果是空怎么办？都是空？一个是空？情况都要考虑清楚。

只要取了节点的左右孩子，还想取它的value，就要想到，判断是否是None。看看代码随想录的解答吧

我的代码：目标删除节点的右孩子，往目标删除节点的左孩子的最右去接

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

        if root.val < key :
            root.right = self.deleteNode(root.right,key)
            
        elif root.val > key :
            root.left = self.deleteNode(root.left,key)
        else :
            node = root.left        
            pre = root.right
            if node == None and pre == None: # 左右均为空
                return None
            elif node == None : # 左为空
                return pre
            # 这里我觉得是，我是让右孩子向右接，所以 pre 为空，无所谓
            else :
                
                while node.right :
                    node = node.right
                    
                node.right = pre
                return root.left

        return root

删除二叉搜索树中的节点

卡哥给出的，普通树的删除方法，以及迭代法，都先不做学习了，先掌握最基本的递归法。

根据卡哥给的思路，对上面自己的代码进行了小修改，思路是：目标删除节点的左孩子，往目标删除节点的右孩子的最左去接。

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

        if root.val < key :
            root.right = self.deleteNode(root.right,key)
            
        elif root.val > key :
            root.left = self.deleteNode(root.left,key)
        else :
            node = root.left        
            pre = root.right
            if node == None and pre == None: # 左右都为空
                return None
            elif node == None : # 左为空
                return pre
            elif pre == None : # 右为空
                return node
            else :
                while pre.left :
                    pre = pre.left      
                pre.left = node
                return root.right

        return root

本题对于第五步，删除拼接的情况，本来就有两种选择，上面我都提到了，左接右，右接左。

代码随想录的代码：

class Solution:
    def deleteNode(self, root, key):
        if root is None:
            return root
        if root.val == key:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                cur = root.right
                while cur.left is not None:
                    cur = cur.left
                cur.left = root.left
                return root.right
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

修剪二叉搜索树

不会，理不清处理逻辑。

自己写的错误代码：

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root == None :
            return None
        if root.val >= low and root.val <= high :
            root.left = self.trimBST(root.left,low,high)
            root.right = self.trimBST(root.right,low,high)
            return root   
        elif root.val < low :
            head = root.right
            if head == None :
                return None
            head.left = self.trimBST(head.left,low,high)
            head.right = self.trimBST(head.right,low,high)
            return head
        elif root.val > high :
            head = root.left
            if head == None :
                return None
            head.left = self.trimBST(head.left,low,high)
            head.right = self.trimBST(head.right,low,high)
            return head

看看代码随想录的解答。这是一个思维转变的问题，好好理解。

修剪二叉搜索树

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if root is None:
            return None
        if root.val < low:
            # 寻找符合区间 [low, high] 的节点
            return self.trimBST(root.right, low, high)
        if root.val > high:
            # 寻找符合区间 [low, high] 的节点
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)  # root.left 接入符合条件的左孩子
        root.right = self.trimBST(root.right, low, high)  # root.right 接入符合条件的右孩子
        return root

这道题非常非常重要。迭代法先不做学习了、

将有序数组转换为二叉搜索树

取数组中间数值，递归构造即可。

把二叉搜索树转换为累加树

之前做过类似的题。

class Solution:
    def __init__(self):
        self.last = None
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None :
            return None
        
        root.right = self.convertBST(root.right)
        if self.last :
            root.val += self.last.val
        self.last = root
        root.left = self.convertBST(root.left)

        return root

迭代法：

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None :
            return None
        st = []
        cur = root
        last = None
        while st or cur :
            if cur :
                st.append(cur)
                cur = cur.right

            else :
                cur = st.pop()
                if last :
                    cur.val += last.val
                last = cur
                cur = cur.left

        return root