CSDN话题挑战赛第2期
参赛话题：算法题解

LeetCode Cookbook 树（1）

正好赶上活动 最近一周把 树 有关的题给做了三十来道，将进行一个系统整理，有关算法的复杂度可以点击链接题目查看，这里就不进行专门的叙述。树 这部分内容挺多的 想分成4~5部分来说，努力，奋斗！

144. 二叉树的前序遍历（model-I 排序）

题目链接：144. 二叉树的前序遍历
题目大意：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

例如：

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

解题思路： 两大类方法 三种写法 。方法（一） 深度优先搜索（DFS）、与方法（三） 广度优先搜索（BFS）模板2 通用于前中后遍历， 方法（二） 广度优先搜索（BFS）模板1 适用于前后遍历与层序遍历

方法（一） 深度优先搜索（DFS）

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # DFS
        def preOrder(node: Optional[TreeNode]) -> None:
            if node is None: return 
            ans.append(node.val)
            if node.left: preOrder(node.left)
            if node.right: preOrder(node.right)
        
        ans = list()
        preOrder(root)
        return ans

方法（二） 广度优先搜索（BFS）模板1

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # BFS 模板1
        if root is None: return []
        ans = list()
        q = collections.deque([root])
        while q:
            node = q.pop()
            ans.append(node.val)
            if node.right: q.append(node.right)
            if node.left:q.append(node.left)
        return ans

方法（三） 广度优先搜索（BFS）模板2

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # BFS 模板2
        ans = list()
        q = collections.deque([(0,root)])
        while q:
            flag,cur = q.pop()
            if cur is None: continue
            if flag == 0:
                q.append((0,cur.right))
                q.append((0,cur.left))
                q.append((1,cur))
            else:
                ans.append(cur.val)
        return ans

94. 二叉树的中序遍历（model-I 排序）

题目链接：94. 二叉树的中序遍历
题目大意：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

例如：

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

解题思路： 两大类方法 三种写法 。方法（一） 深度优先搜索（DFS）、与方法（三） 广度优先搜索（BFS）模板2 通用于前中后遍历。

方法（一） 深度优先搜索（DFS）

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 前中后 指的都是 根节点所在位置
        # 中序遍历 LDR

        # DFS
        def inOrder(node: Optional[TreeNode]) -> None:
            if node is None: return
            if node.left: inOrder(node.left)
            ans.append(node.val)
            if node.right: inOrder(node.right)  
        ans = list()
        inOrder(root)
        return ans

方法（三） 广度优先搜索（BFS）模板2

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # BFS 标记 模板
        ans = list()
        q = collections.deque([(0,root)])
        while q:
            flag,cur = q.pop()
            if cur is None: continue
            if flag == 0:
                q.append((0,cur.right))
                q.append((1,cur))
                q.append((0,cur.left))
            else:
                ans.append(cur.val)
        return ans

144. 二叉树的后序遍历（model-I 排序）

题目链接：144. 二叉树的后序遍历
题目大意：给你二叉树的根节点 root ，返回它节点值的 后序 遍历。

例如：

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

解题思路： 两大类方法 三种写法 。方法（一） 深度优先搜索（DFS）、与方法（三） 广度优先搜索（BFS）模板2 通用于前中后遍历， 方法（二） 广度优先搜索（BFS）模板1 适用于前后遍历与层序遍历

方法（一） 深度优先搜索（DFS）

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        def postOrder(node: Optional[TreeNode]) -> None:
            if node is None: return 
            if node.left: postOrder(node.left)
            if node.right: postOrder(node.right)
            ans.append(node.val)
        
        ans = list()
        postOrder(root)
        return ans

方法（二） 广度优先搜索（BFS）模板1

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # BFS 模板1
        if root is None: return []
        ans = list()
        q = collections.deque([root])
        while q:
            node = q.pop()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            ans.append(node.val)
        return ans[::-1]

方法（三） 广度优先搜索（BFS）模板2

        # BFS 模板2
        ans = list()
        q = collections.deque([(0,root)])
        while q:
            flag,cur = q.pop()
            if cur is None: continue
            if flag == 0:
                q.append((1,cur))
                q.append((0,cur.right))
                q.append((0,cur.left))
            else:
                ans.append(cur.val)
        return ans

102. 二叉树的层序遍历（model-I 排序）

题目链接：102. 二叉树的层序遍历
题目大意：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

例如：

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

解题思路： 广度优先搜索。

# 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]]:
        
        # BFS 模板
        if root is None: return []
        ans = list()
        q = collections.deque([root])
        while q:
            lay,layval = list(),list()
            for node in q:
                layval.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            q = lay
            ans.append(layval)
        return ans

107. 二叉树的层序遍历 II（model-I 排序 扩展1）

题目链接：107. 二叉树的层序遍历 II
题目大意：给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

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

解题思路： 广度优先搜索。

# 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:        
        if root is None: return []
        q = collections.deque([root])
        ans = list()
        while q:
            lay,layer = list(),list()
            for node in q:
                layer.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            q = lay
            ans.append(layer)
        return ans[::-1]

103. 二叉树的锯齿形层序遍历（model-I 排序 扩展2）

题目链接：102. 二叉树的层序遍历
题目大意：给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

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

解题思路： 广度优先搜索，加个旗帜。

# 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]]:
        if root is None: return []
        q = collections.deque([root])
        ans = list()
        flag = False
        while q:
            lay,layer = list(),list()
            flag = ~flag 
            for node in q:
                layer.append(node.val)
                if node.left: lay.append(node.left)
                if node.right: lay.append(node.right)
            q = lay
            ans += [layer] if flag else [layer[::-1]]
        return ans

104. 二叉树的最大深度（model-II 深度）

题目链接：104. 二叉树的最大深度
题目大意：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

例如：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3 。
)

解题思路： 深度优先搜索。

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

104. 二叉树的最小深度（model-II 深度）

题目链接：104. 二叉树的最小深度
题目大意：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

例如：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最小深度 2 。
)

解题思路： 稍微复杂些 仍是深度优先搜索。

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        if root.left is None: return self.minDepth(root.right)+1
        if root.right is None: return self.minDepth(root.left)+1
        return min(self.minDepth(root.left),self.minDepth(root.right))+1

563. 二叉树的坡度（model-II 深度 扩展1）

题目链接：104. 二叉树的最大深度
题目大意：给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。整个树 的坡度就是其所有节点的坡度之和。

例如：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3 。

输入：root = [1,2,3]
输出：1
解释：
节点 2 的坡度：|0-0| = 0（没有子节点）
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
坡度总和：0 + 0 + 1 = 1

输出：15
解释：
节点 3 的坡度：|0-0| = 0（没有子节点）
节点 5 的坡度：|0-0| = 0（没有子节点）
节点 7 的坡度：|0-0| = 0（没有子节点）
节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ）
坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15

解题思路： 深度优先搜索。

# 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:
    # py3 定义全局变量 ans
    def __init__(self):
        self.ans = 0

    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.ans

    def dfs(self,node:Optional[TreeNode]) -> int:
        if node is None: return 0
        L = self.dfs(node.left)
        R = self.dfs(node.right)
        self.ans += abs(L-R)
        return node.val + L + R

662. 二叉树最大宽度（model-III 宽度 线段树基础）

题目链接：104. 二叉树的最小深度
题目大意：给你一棵二叉树的根节点 root ，返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。题目数据保证答案将会在 32 位 带符号整数范围内。

例如：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

解题思路： 两种方法，DFS 以及 BFS。

方法（一）

# 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 widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        # DFS
        levelLeft = {}
        def DFS(node: Optional[TreeNode],depth: int,index: int) -> int:
            if node is None: return 0
            if depth not in levelLeft:
                levelLeft[depth] = index
            return max(index - levelLeft[depth]+1,
                    DFS(node.left,depth+1,index*2),
                    DFS(node.right,depth+1,index*2+1))
        return DFS(root,1,1)

方法（二）

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # BFS
        ans = 1
        q =[[root,1]]
        while q:
            tmp = []
            for node,index in q:
                if node.left:
                    tmp.append([node.left,index*2])
                if node.right:
                    tmp.append([node.right,index*2+1])
            ans = max(ans,q[-1][1] - q[0][1] + 1)
            q = tmp
        return ans

100. 相同的树（model-IV）

题目链接：100. 相同的树
题目大意：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

例如：

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

输入：p = [1,2], q = [1,null,2]
输出：false

解题思路：DFS。

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None: return True
        elif p and q:
            if p.val != q.val: return False
            else:
                return self.isSameTree(p.left,q.left) and \
                self.isSameTree(p.right,q.right)
        else:
            return False

226. 翻转二叉树（model-IV）

题目链接：226. 翻转二叉树
题目大意：给你一棵二叉树的根节点 root ，返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。题目数据保证答案将会在 32 位 带符号整数范围内。

例如：

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

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

解题思路： DFS。

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

101. 对称二叉树（model-IV 扩展）

题目链接：101. 对称二叉树
题目大意：给你一个二叉树的根节点 root ， 检查它是否轴对称。

例如：

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

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

解题思路： 100. 相同的树 + 226. 翻转二叉树

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None: return True
        return self.isSametree(self.invertTree(root.left),root.right)
        
    def isSametree(self,p: Optional[TreeNode],q: Optional[TreeNode]) -> bool:
        if p is None and q is None: return True
        elif p and q:
            if p.val != q.val: return False
            else:
                return self.isSametree(p.left,q.left) and \
                self.isSametree(p.right,q.right)
        else:
            return False
        
    def invertTree(self,root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None: return 
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left,root.right = root.right,root.left
        return root

总结

   树 这部分内容很抽象，做起来挺吃力地！ 不过加快速度 争取国庆之前 做完整理完，这部分需要好好记一下，树的题有一个总体的解题思路，把复杂的问题往这些简单的基础题上靠，树的难题很大一部分就是题意复杂或包含的基础步骤众多，所以细细品味，加油学习。