算法训练营 day14 ｜ 二叉树 part02

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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.right)
        self.invertTree(root.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 root is None:
            return root
        
        queue = collections.deque([root])
        while queue:
            for i in range(len(queue)):
                cur = queue.popleft()
                cur.left, cur.right = cur.right, cur.left
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return root   

101. 对称二叉树

# 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.compare(root.left, root.right)
    
    def compare(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
        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
        

总结：代码使用的是递归法，当然使用迭代法，或者层序遍历都可以实现

104. 二叉树的最大深度

# 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:
        return self.getdepth(root)
    
    def getdepth(self, node):
        if node is None:
            return 0
        leftheight = self.getdepth(node.left) 
        rightheight = self.getdepth(node.right)
        height = 1 + max(leftheight, rightheight)
        return height

总结：代码使用递归法，后序遍历。使用层序遍历也很好做，框架写完，返回len(res)即可。

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:
        return self.getmindepth(root)
    
    def getmindepth(self, node):
        if node is None:
            return 0
        res = 0
        leftdepth = self.getmindepth(node.left)
        rightdepth = self.getmindepth(node.right)
        if node.left != None and node.right == None:
            return leftdepth + 1
        if node.right != None and node.left == None:
            return rightdepth + 1
        res = min(leftdepth, rightdepth) + 1
        return res

迭代法： 

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

总结：本题的主要点在于，只有当左右子树同时为空时才能返回当前深度。

题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

什么是叶子节点，左右孩子都为空的节点才是叶子节点！