代码随想录算法训练营第14天|226.翻转二叉树、101. 对称二叉树、104. 二叉树的最大深度、111.二叉树的最小深度

打卡Day14

1.226.翻转二叉树
2.101. 对称二叉树
- 扩展
- - 100. 相同的树
  - 572. 另一棵树的子树
3.104. 二叉树的最大深度
- 扩展
- - 559.n叉树的最大深度
3.111.二叉树的最小深度

1.226.翻转二叉树

题目链接：226.翻转二叉树
文档讲解：代码随想录

（1）递归法

思路：以二叉树的递归遍历为基础。确定递归函数的参数和返回值，输入树节点，输出根节点；确定终止条件，节点为空；确定逻辑，以前序遍历为例，先处理中节点，将其左右孩子对换，然后处理左节点，再处理右节点。

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        root.left, root.right = root.right,  root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

后序遍历：

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

中序遍历：
这里会把某些节点的左右孩子翻转两次。遍历到左节点 A，将其左右孩子对调，然后返回根节点，翻转根节点的左右孩子后，再遍历的右节点还是 A，这样会导致 A 翻转两次。

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        self.invertTree(root.left)
        root.left, root.right = root.right,  root.left
        self.invertTree(root.left)
        return root

（2）迭代法

前序遍历：

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: 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

后序遍历：

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

中序遍历：

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: 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

（3）层序遍历

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        queue = collections.deque([root])
        while queue:
            size = len(queue)
            for i in range(size):
                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

2.101. 对称二叉树

题目链接：101. 对称二叉树
文档讲解：代码随想录

思路：
比较是否是对称二叉树，不是比较左右节点是否一致，而是比较跟节点的左右子树，所以在递归遍历的过程中，要同时遍历两棵树。要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。所以要采用后序遍历，先把左右孩子进行比较，再处理中节点将结果返回根节点。

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        return self.compare(root.left, root.right)
    
    def compare(self, left, right):
        #首先排除空节点的情况
        if left == None and right != None: return False
        if left != None and right == None: return False
        if left == None and right == None: return True
        #再排除节点不空但值不同的情况
        if 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

迭代法：关键是将需要比较的节点相邻放入队列或者栈

（1）使用队列

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: 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
            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

（2）使用栈

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        stack = []
        stack.append(root.left)
        stack.append(root.right)
        while stack:
            leftNode = stack.pop()
            rightNode = stack.pop()
            if not leftNode and not rightNode:
                continue
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            stack.append(leftNode.left)
            stack.append(rightNode.right)
            stack.append(leftNode.right)
            stack.append(rightNode.left)
        return True

层次遍历：

思路：比较每层的节点值是否对称

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        queue = collections.deque([root.left, root.right])
        while queue:
            size = len(queue)
            if size % 2 != 0:
                return False
            level = []
            for i in range(size):
                node = queue.popleft()
                if node:
                    level.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    level.append(None)
            if level != level[::-1]:
                return False
        return True

扩展

100. 相同的树

题目链接：100

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return self.compare(p,q)
    
    def compare(self, node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        
        leftside = self.compare(node1.left, node2.left)
        rightside = self.compare(node1.right, node2.right)
        isSame = leftside and rightside
        return isSame

572. 另一棵树的子树

题目链接：572

对于是否是否包含 subroot 的递归思路：确定输入为 root 和 subRoot；终止条件是 root 节点为空；比较逻辑是，首先确定compare(root, subRoot)，如果不是则比较左右节点。

class Solution(object):
    def isSubtree(self, root, subRoot):
        """
        :type root: TreeNode
        :type subRoot: TreeNode
        :rtype: bool
        """

        #分两步：是否包含subroot；是否包含子树
        if not root:
            return False
        
        if self.compare(root, subRoot):
            return True
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def compare(self, node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        leftside = self.compare(node1.left, node2.left)
        rightside = self.compare(node1.right, node2.right)
        isSame = leftside and rightside
        return isSame

3.104. 二叉树的最大深度

题目链接：104. 二叉树的最大深度
文档讲解：代码随想录

这道题昨天用层序遍历的方式做过，今天主要掌握递归方法。前序遍历求的是深度，深度是指从根节点到该节点的最长简单路径边的条数或者节点数。后序遍历求的是高度，高度是指从该节点到叶子节点的最长简单路径边或者节点数。根节点的高度就是二叉树的最大深度。

（1）后序遍历
思路：确定递归函数输入输出，参数是树的根节点，返回值是 int 类型；确定终止条件，节点为空，则返回高度为0，因为是从1开始计数的；确定逻辑，先求左子树的高度，再求右子树的高度，最后取左右子树的最大高度再加一。

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        leftHeight = self.maxDepth(root.left)
        rightHeight = self.maxDepth(root.right)
        depth = 1 + max(leftHeight, rightHeight)
        return depth

（2）前序遍历

class Solution(object):
    def __init__(self):
        self.res = float('-inf')
    
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        self.getDepth(root, 1)
        return self.res

    def getDepth(self, node, depth):
        if not node:
            return
        self.res = max(self.res, depth)
        if node.left:
            self.getDepth(node.left, depth + 1)
        if node.right:
            self.getDepth(node.right, depth + 1)

（2）迭代法就是昨天学过的层序遍历。

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

扩展

559.n叉树的最大深度

题目链接：559

递归：

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root:
            return 0
        max_depth = 1
        for child in root.children:
            max_depth = max(max_depth, self.maxDepth(child) + 1)
        return max_depth

迭代：

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root:
            return 0
        queue = collections.deque([root])
        depth = 0

        while queue:
            depth += 1
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                for child in node.children:
                    queue.append(child)
        return depth

使用栈：

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if not root:
            return 0
        maxx = 0
        stack = [(root, 1)]
        while stack:
            node, depth = stack.pop()
            maxx = max(maxx, depth)
            for child in node.children:
                stack.append((child, depth + 1))
        return maxx

3.111.二叉树的最小深度

题目链接：111.二叉树的最小深度
文档讲解：代码随想录

求二叉树的最小深度和最大深度的差别主要在于处理左右孩子不为空的逻辑。不能处理为，左右子树的高度最小值加一。如图所示，当左子树为空时，该二叉树的最小深度应该是右子树最小深度再加一。

在这里插入图片描述
后序遍历：

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and root.right:
            return 1 + self.minDepth(root.right)
        if root.left and not root.right:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

前序遍历：

class Solution(object):
    def __init__(self):
        self.res = float('inf')
    
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        self.getMinDepth(root, 1)
        return self.res

    def getMinDepth(self, node, depth):
        if not node:
            return

        if not node.left and not node.right:
            self.res = min(self.res, depth)
        
        if node.left:
            self.getMinDepth(node.left, depth + 1)
        if node.right:
            self.getMinDepth(node.right, depth + 1)

迭代法：

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        depth = 0
        queue = collections.deque([root])
        while queue:
            depth += 1
            size = len(queue)
            for i in range(size):
                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