101. 对称二叉树

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

思路

层序遍历，判断每一层是否为对称。注意需要记录当前在第几层，还需要判断当前层的长度是否是 2^n。但是，这种方法只考虑了满二叉树的情况。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        que = deque()
        if root:
            que.append(root)
        count = 0
        while que:
            cur_level = []
            for _ in range(len(que)):
                cur = que.popleft()
                cur_level.append(cur.val)

                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)

            if len(cur_level) == 2 ** count:
                l, r = 0, len(cur_level) - 1
                while l <= r:
                    if cur_level[l] != cur_level[r]:
                        return False
                    else:
                        l += 1
                        r -= 1
            else:
                return False
            count += 1
        return True

正确思路

对于根节点，应该要判断其两个子树是否是对称的，所以需要同时遍历两个子树。注意，两个子树的遍历方法也需要对称，本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。（？）

递归三部曲：

参数和返回类型：传入左右子树，返回两个子树是否相等
终止条件：比较两个子节点
单层递归逻辑：分别比较外侧和内侧节点是否相等

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        def treverse(l, r):

            if l != None and r == None:
                return False
            elif l == None and r != None:
                return False
            elif l == None and r == None:
                return True
            else:
                if r.val != l.val:
                    return False
                else:
                    # 左右节点都不为空，且节点相等，开始遍历子节点
                    inter = treverse(l.right, r.left)
                    out = treverse(l.left, r.right)
                    
                    if out & inter:
                        return True
                    else:
                        return False
        
        if root:
            return treverse(root.left, root.right)
        else:
            return False

104.二叉树的最大深度

层序遍历，返回 res 的长度

111.二叉树的最小深度

层序遍历，节点的左右都为空时，则返回当前深度

222.完全二叉树的节点个数

完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点

思路1

直接遍历

思路2

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def treverse(node):
            if node!= None:
                leftd, rightd = 1, 1
                rightn = node.right
                leftn = node.left
                while rightn:
                    rightd += 1
                    rightn = rightn.right
                while leftn:
                    leftd += 1
                    leftn = leftn.left
                if leftd == rightd:
                    return 2 ** leftd - 1

                else:
                    return treverse(node.left) + treverse(node.right) + 1
            else:
                return 0
        return treverse(root)

110.平衡二叉树

link

平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

使用后序遍历：

参数：当前传入节点。返回值：以当前传入节点为根节点的树的高度。
递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0
判断以当前传入节点为根节点的二叉树是否是平衡二叉树：其左子树高度和其右子树高度的差值。代码中返回 -1 表示当前已经有子树不满足平衡条件了，所以不用进行后续比较，直接退出即可。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def treverse(node):
            if node != None:
                leftd = treverse(node.left)
                rightd = treverse(node.right)
                if leftd == -1:
                    return -1
                if rightd == -1:
                    return -1
                if abs(leftd - rightd) > 1:
                    return -1
                else:
                    return 1 + max(leftd, rightd)
            else:
                return 0
        
        if treverse(root) == -1:
            return False
        else:
            return True