树的题目一般都是递归能够解决，类似于DP问题，找到大树化小树的方式，同时找到出口（即叶子节点或满足条件的清空）

翻转二叉树

翻转的原理很简单，让left等于right即可，python代码如下：

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            temp = root.left
            root.left = self.invertTree(root.right)
            root.right = self.invertTree(temp)
        return root

对称二叉树

虽然是easy题目，但是没那么好想到，主要就是要对比左子树和右子树，两棵树对称要保证一棵树的left和另一棵树的right对称，一棵树的right和另一棵树的left对称，且两个数的根节点值相同，python代码如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def helper(self,left_node,right_node):
        if left_node == None and right_node == None: 
            return True
        elif left_node == None or right_node == None: 
            return False
        else:
            return left_node.val == right_node.val and self.helper(left_node.left,right_node.right) and self.helper(left_node.right,right_node.left)

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

从前序与中序遍历序列构造二叉树

前序遍历第一个元素是树的根节点，中序遍历中根节点左边的节点在根节点左边，右边的节点在根节点右边
用python实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0: return None
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:index+1],inorder[:index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root

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

后序遍历最后一个元素是根节点，用python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0: return None
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:index+1],inorder[:index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root

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

层次遍历的方法，python实现如下：

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        stack1,stack2 = [],[]
        if root:
            stack1.append(root)
        while len(stack1) > 0 or len(stack2) > 0:
            if len(stack1) > 0:
                for i in range(len(stack1)):
                    if stack1[i].left:
                        stack2.append(stack1[i].left)
                    if stack1[i].right:
                        stack2.append(stack1[i].right)
                    stack1[i].next = stack1[i+1] if i+1 < len(stack1) else None
                stack1 = []
            else:
                for i in range(len(stack2)):
                    if stack2[i].left:
                        stack1.append(stack2[i].left)
                    if stack2[i].right:
                        stack1.append(stack2[i].right)
                    stack2[i].next = stack2[i+1] if i+1 < len(stack2) else None
                stack2 = []
        return root

求根节点到叶节点数字之和

同之前的类型，找到递归的方式，需要一个helper函数来协助递归，记录当前节点已经走过的节点的value，当当前节点left和right都为空时，为叶子节点，此时返回记录值，其它情况继续遍历，用python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def helper(self,node,cur_val):
        if node.left == None and node.right == None:
            return [int(cur_val)]
        ret = []
        if node.left:
            ret.extend(self.helper(node.left,cur_val+str(node.left.val)))
        if node.right:
            ret.extend(self.helper(node.right,cur_val+str(node.right.val)))
        return ret

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        cur_val = str(root.val)
        ret = self.helper(root,cur_val)
        return sum(ret)

完全二叉树的节点个数

很典型的树的题目的解法，找到递归的方式以及递归截止的情况，用python实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root:
            return self.countNodes(root.left) + self.countNodes(root.right) + 1
        return 0

二叉树的最近公共祖先

这个题目还是找到递归的方式以及满足条件的出口，当前节点是否是祖先需要满足其下包含了p和q两个节点，是否是最近祖先，需要满足不存在其子节点也满足情况，python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def helper(self,node,p,q):
        if node == None:return 0,None
        c0 = 0
        if node == p or node == q: c0 = 1
        c1,t1 = self.helper(node.left,p,q)
        c2,t2 = self.helper(node.right,p,q)
        if c0 + c1 + c2 == 2:
            if t1 == None and t2 == None:
                return c0 + c1 + c2, node
            else:
                return c0 + c1 + c2, t1 if t1 else t2
        else:
            return c0 + c1 + c2, None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        _,node= self.helper(root,p,q)
        return node

二叉树的右视图

用层次遍历的方式解决，取最后一个元素，python实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ret = []
        s1,s2 = [],[]
        if root:s1.append(root)
        while len(s1)>0 or len(s2)>0:
            if len(s1)>0:
                for node in s1:
                    if node.left:s2.append(node.left)
                    if node.right:s2.append(node.right)
                ret.append(s1[-1].val)
                s1 = []
            else:
                for node in s2:
                    if node.left:s1.append(node.left)
                    if node.right:s1.append(node.right)
                ret.append(s2[-1].val)
                s2 = []
        return ret

二叉树的层平均值

层次遍历，这次使用一种新的方法解决，不用双数组了，一个数组就行，记录每一层的长度，每次遍历的时候只遍历这个长度即可，用python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        ret = []
        q = []
        if root:q.append(root)
        while len(q)>0:
            size = len(q)
            i = 0
            s = 0
            # 因为q中的元素是不断变化的，只遍历当前层的元素
            while i<size:
                s += q[i].val
                if q[i].left:q.append(q[i].left)
                if q[i].right:q.append(q[i].right)
                i += 1
            ret.append(s/size)
            q = q[size:]
        return ret

顺便温故一下dfs，用一个dict记录每一层节点的val，遍历所有的节点，并记录节点对应的层数，用python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self,node,level2value,level):
        if level not in level2value:
            level2value[level] = [node.val]
        else:
            level2value[level].append(node.val)
        if node.left:
            self.dfs(node.left,level2value,level+1)
        if node.right:
            self.dfs(node.right,level2value,level+1)
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        level2value = {}
        self.dfs(root,level2value,0)
        return [sum(t[1])/len(t[1]) for t in sorted(level2value.items(),key=lambda x:x[0])]

二叉树的层序遍历

之前使用层序遍历的方法有点问题，还是下面这个方法简单一点：

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ret = []
        q = []
        if root: q.append(root)
        while len(q)>0:
            size = len(q)
            i = 0
            temp = []
            while i<size:
                temp.append(q[i].val)
                if q[i].left:q.append(q[i].left)
                if q[i].right:q.append(q[i].right)
                i += 1
            ret.append(temp)
            q = q[size:]
        return ret

二叉树的锯齿形层序遍历

主要是遍历的时候，先存储左右哪个节点，按右边存储的需要翻转，用python实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ret = []
        q = []
        if root:q.append(root)
        flag = True
        while len(q)>0:
            size = len(q)
            temp = []
            if flag:
                i = 0
                while i<size:
                    temp.append(q[i].val)
                    if q[i].left:q.append(q[i].left)
                    if q[i].right:q.append(q[i].right)
                    i += 1
                flag = False
                q = q[size:]
            else:
                i = size-1
                while i>=0:
                    temp.append(q[i].val)
                    if q[i].right:q.append(q[i].right)
                    if q[i].left:q.append(q[i].left)
                    i -= 1
                flag = True
                q = q[size:]
                # 翻转数组
                i = 0
                s = len(q)-1
                while i<s:
                    t = q[i]
                    q[i] = q[s]
                    q[s] = t
                    i+=1
                    s-=1
            ret.append(temp)
        return ret

突然想到一种简化方法，不用翻转数组，先按从左到右的顺序存储，然后按从右到左的顺序存储，自然而然就是z字形的输出，同时需要每次遍历的时候从最后往前遍历：

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ret = []
        q = []
        if root:q.append(root)
        flag = True
        while len(q)>0:
            size = len(q)
            temp = []
            i = size-1
            while i>=0:
                temp.append(q[i].val)
                if flag:
                    if q[i].left:q.append(q[i].left)
                    if q[i].right:q.append(q[i].right)
                else:
                    if q[i].right:q.append(q[i].right)
                    if q[i].left:q.append(q[i].left)
                i -= 1
            flag = not flag
            q = q[size:]
            ret.append(temp)
        return ret

二叉搜索树的最小绝对差

二叉搜索树的中序遍历是一个有序的数组，最小绝对差只需要遍历相邻元素的差即可

# 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 dfs(self,root,arr):
        if root.left:
            self.dfs(root.left,arr)
        arr.append(root.val)
        if root.right:
            self.dfs(root.right,arr)

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        arr = []
        self.dfs(root,arr)
        min_value = arr[1]-arr[0]
        for i in range(1,len(arr)-1):
            min_value = min(arr[i+1]-arr[i],min_value)
        return min_value

二叉搜索树中第K小的元素

这个题目还是利用二叉搜索树的中序遍历是一个有序数组的思路，遍历到第k个位置就停止遍历，我用的方法是记录第k个数，直到第k个数找到停止遍历，比较容易出错，但容易想到：

# 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 dfs(self,root,index,k):
        k_value = None
        if root.left:
            k_value,index = self.dfs(root.left,index,k)
            if k_value!=None:return k_value,index
        index += 1
        if index == k:
            return root.val,index
        if root.right:
            k_value,index = self.dfs(root.right,index,k)
        return k_value,index
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        k_value,index = self.dfs(root,0,k)
        print(k_value,index)
        return k_value

leetcode题解中有一种比较好理解，不容易出错的方法，如下所示：

# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

验证二叉搜索树

二叉搜索树中当前节点的值要大于左子树中最大的值，小于右子树中最小的值，需要借助一个函数来记录当前树的最小值和最大值，仍旧用递归的思路：

# 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 helper(self,root):
        if root.left == None and root.right == None: return True,root.val,root.val
        if root.left and root.right:
            status,l1,l2 = self.helper(root.left)
            status2,r1,r2 = self.helper(root.right)
            flag = status and status2 and l2 < root.val and root.val < r1
            return flag,l1,r2
        if root.left:
            status,l1,l2 = self.helper(root.left)
            return status and root.val > l2, l1,root.val
        if root.right:
            status,r1,r2 = self.helper(root.right)
            return status and root.val < r1, root.val,r2

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        status,_,_ = self.helper(root)
        return status