算法刷题（三） - 二叉树的结构

发表于 | 阅读次数：

树的子结构

一开始的思路是对 A、B 分别进行二叉树遍历，判断A.val数组是否包含B.val的数组，也过了绝大部分测试用例，但最后发现仍然有些特殊情况不符合这个条件，遂放弃。题解的这个递归的方法并不是很好想，若 B 是 A 的子结构，B 的根节点可以是 A 的任何一个节点，因此任务拆解为，先遍历 A 中的每个节点（isSubStructure），再判断树 A 中 以该节点为根节点的子树是否包含树 B（recursion）。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:  # 约定空树不是任意一个树的子结构
            return False
        def recursion(A, B):
            if not B:  # 树 B 遍历完毕，说明 B 中节点在 A 中均有对应
                return True
            if (not A) or (A.val != B.val):  # 树 A 先遍历完毕，说明 B 中存在 A 中没有的结构；或两棵树对应节点的值不等
                return False
            return recursion(A.left, B.left) and recursion(A.right, B.right)

        return recursion(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)  # 从 A 的根节点 / A 的左子树根节点/ A 的右子树根节点开始判断

二叉树的镜像

将右节点递归的返回值作为左节点，左节点递归的返回值作为右节点 

1
2
3
4
5
6
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return
        root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
        return root

这个遍历并交换的方法更容易理解。 

1
2
3
4
5
6
7
8
9
10
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        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

对称的二叉树

做完镜像二叉树以后，一个惯性方法是创建root的镜像树，再判断两棵树是否相同。可通过，但是要注意创建镜像树时对root进行深拷贝。

这题的思路其实和上面的树的子结构有些相似，同样是递归遍历两棵树（这里是同一棵树的左子树和右子树），当同时越过叶节点时，两棵树对称，只有一颗树越过叶节点或值不相等时不对称。不同的地方在于，递归的递推条件应该是对比左子树的左子树与右子树的右子树，左子树的右子树与右子树的左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
            
        def recur(A, B):
            if not A and not B:
                return True
            elif not A:
                return False
            elif not B:
                return False
            if A.val != B.val:
                return False
            return recur(A.left, B.right) and recur(A.right, B.left)
            
        return recur(root.left, root.right)