前言

今天是算法训练营的第十四天，今天的题目总体难度比较简单，不过还是挺考思维活性的。

226.翻转二叉树

题目链接：226. 翻转二叉树

题目描述：

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

思路

刚看到这道题还是有点懵逼的，如果要把整棵树都翻转，实际上只要把每个节点的左右孩子翻转一下即可。关键在于要使用哪种遍历顺序，这道题前序和后序都可行，但是中序遍历不可，需要注意中序遍历每次翻转左右孩子时，翻转的具体是哪个节点的左右孩子，如果继续依照前序、后序方式翻转将导致左右孩子翻转两次，约等于没翻转。

递归法写法

后序遍历和前序差不多，只是改了一下处理顺序，此处只展示前序遍历

# 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 not root:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

迭代法写法

# 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 not root:
            return root
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
        return root

层序遍历写法

# 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 not root:
            return root
        queue = collections.deque([root])
        while queue:
            levelSize = len(queue)
            for _ in range(levelSize):
                node = queue.popleft()
                node.left, node.right = node.right, node.left
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        return root

101.对称二叉树

题目链接：101. 对称二叉树

题目描述：

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

思路

比较二叉树是否对称，实际上还是在比较每一个左孩子的左孩子是否和右孩子的右孩子相等，左孩子的右孩子是否和右孩子的左孩子相等。由于是要对孩子进行比较，所以用后序遍历比较合适，递归逻辑是不断比较根节点左右两颗子树的内外侧是否相等，如果全部相等则是对称二叉树。

不过，这道题依然可以使用层序遍历来解决，并且层序遍历似乎更加简单，我们只需要把每一层的内容记录下来，再将每一层内容倒序与正序比较是否相等即可。

递归写法

# 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 compare(self,left, right):
        if left == None and right == None:
            return True
        elif left != None and right == None:
            return False
        elif left == None and right != None:
            return False
        elif left.val != right.val:
            return False

        outside = self.compare(left.left, right.right)
        inside = self.compare(left.right, right.left)
        isSame = outside and inside
        return isSame

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left, 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return root
        queue = collections.deque([root])
        while queue:
            levelSize = len(queue)
            vals = []
            for i in range(levelSize):
                node = queue.popleft()
                if node:
                    vals.append(node.val)              
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    vals.append(None)
            if vals[::] != vals[::-1]:
                return False
        return True

104.二叉树的最大深度

题目链接：104. 二叉树的最大深度

题目描述：

给定一个二叉树 root ，返回其最大深度。

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

思路

刚看到这道题的思路是使用层序遍历，因为是逐层处理，所以只要再每一层都进行记录就可以得到最大深度了。

层序遍历做法

# 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 not root:
            return 0
        queue = collections.deque([root])
        ans = 0
        while queue:
            levelSize = len(queue)
            for i in range(levelSize):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans += 1
        return ans

111.二叉树的最小深度

题目链接：111. 二叉树的最小深度

题目描述：

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

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

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

思路

这道题如果用层序遍历解决，思路和求最大深度差不多，只是换了个方向而已，我觉得使用层序遍历解决这类问题比较方便，所以暂时只学习层序遍历解法

层序遍历解法

# 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 not root:
            return 0 
        queue = collections.deque([root])
        ans = 0
        while queue:
            levelSize = len(queue)
            for i in range(levelSize):
                node = queue.popleft()
                if not node.left and not node.right:
                    return ans + 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans += 1
        return ans

总结

今天的题目总体来说还是挺有趣的，最大深度和最小深度那边用层序遍历水了一下，目前二叉树的几种遍历方式还是层序遍历最深得我心。