灵神基础算法精讲-10-学习笔记

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路

相同的定义：首先根节点必须是相同的，然后就看左子树是否相同，右子树是否相同，这样可以看出要解决的子问题，就是左边两颗子树是否相同，以及右边两颗子树是否相同，这样就可以用递归来解决了，边界条件是如果两个子节点都是空，就返回 true，否则返回 false。

首先判断边界条件，如果 p 和 q 其中一个为空，那么只有两个节点都为空才返回 true，然后先判断节点值是否一样，再递归判断左子树是否一样和右子树是否一样。

做法

def isSameTree(p, q):
    if p is None or q is None:
        return p is q
    return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树

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

思路

根节点已经是对称的，不用管，那么就需要看左子树和右子树是否对称，和上一题类似，首先看根节点是否相同，然后递归左边的左子树和右边的右子树，以及左边的右子树和右边的左子树，看它们是否对称。

做法

def isSameTree(p, q):
    if p is None or q is None:
        return p is q
    return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)

def isSymmetric(root):
    return isSameTree(root.left, root.right)

110. 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树：是指该树所有节点的左右子树的高度相差不超过 1。

思路

通过递归得到左右两棵子树的高度，算一下高度差的绝对值是否小于等于 1。还需要思考一个问题，如果在递归中发现这棵树是不平衡的，正常返回的是树的高度，它是个非负数，所以可以利用负数，用 -1 表示这棵树是不平衡的。如果发现不平衡，就把 -1 返回给父节点，父节点收到 -1 也立刻返回，就不再继续递归了，因此只要返回了 -1，这个 -1 会不断返回，一路返回到递归调用的入口，最后在递归入口处判断一下拿到的数是不是 -1。

做法

def isBalanced(root):
    def get_height(node):
        if node is None:
            return 0
        left_height = get_height(node.left)
        if left_height == -1:
            return -1
        right_height = get_height(node.right)
        if right_height == -1 or abs(left_height - right_height) > 1:
            return -1
        return max(left_height, right_height) + 1
    return get_height(root) != -1

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路

先递归右子树，再递归左子树，有两个问题，第一个问题是怎么把答案记下来，第二个问题是怎么判断这个节点是否需要记录到答案中，这里可以用之前讲的一种方法，在递归的同时记录一个节点个数，或者说递归深度，如果递归深度等于答案的长度，那么这个节点就需要记录到答案中，比如一棵树一开始深度为0，那么答案初始化为空，长度也为0，那么就把根节点记录进去，现在答案长度为 1，那么继续递归深度为 1，答案长度也为 1，再次记录进去。当右子树递归完了，接着递归左子树，由于深度都小于答案的长度，所以这些都不记录进去，直到碰到深度等于答案长度的节点，将其记录进答案。

首先初始化答案为空，然后定义一个递归函数，传入节点和当前的深度。先判断一下边界条件，如果节点为空，就直接返回，如果深度等于答案的长度，就把它记录到答案里，然后递归右子树和左子树，最后从根节点调用进去就可以返回答案了。

做法

def rightSideView(root):
    
    ans = []
    def f(node, depth):
        if node is None:
            return 
        if depth == len(ans):
            ans.append(node.val)
        f(node.right, depth + 1)
        f(node.left, depth + 1)
    f(root, 0)
    return ans