代码随想录算法训练营Day 13| 226.翻转二叉树 , 101. 对称二叉树

题目简介

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

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

初见思路

226. 递归思路很好想，想边界条件叶节点，把根节点的左右子节点对调就行了。

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

## 迭代法
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        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

##  迭代的升级 - 层序遍历
from collections import deque
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return

        queue = deque([root])
        while queue:
            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. 迭代法也还比较好想，重点是想清楚边界条件：叶子节点的时候返回真，树的高度不同返回假，值不同的时候返回假，

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        return self.isEqual(root,root)
            
    
    def isEqual(self,left_node,right_node)->bool:
        if not left_node and not right_node:
            return True

        if not left_node or not right_node:
            return False

        if left_node.val != right_node.val:
            return False

        return self.isEqual(left_node.left, right_node.right) and self.isEqual(left_node.right, right_node.left)

## 迭代法层序遍历
from collections import deque
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        queue = deque([root.left,root.right])

        while queue:
            size = len(queue)
            if size % 2 != 0:
                return False
            
            level_nodes = list()
            for _ in range(size):
                node = queue.popleft()
                if node:
                    level_nodes.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
                else:
                    level_nodes.append(None)
            
            if level_nodes != level_nodes[::-1]:
                return False

        return True
        

复盘思路

其实对于以上两个问题迭代就够了，迭代法只是用于理解二叉树的操作而已。

重点难点

https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

今日收获

1. 二叉树递归、迭代遍历法