树的子结构
一开始的思路是对 A、B
分别进行二叉树遍历,判断A.val
数组是否包含B.val
的数组,也过了绝大部分测试用例,但最后发现仍然有些特殊情况不符合这个条件,遂放弃。题解的这个递归的方法并不是很好想,若
B 是 A 的子结构,B 的根节点可以是 A
的任何一个节点,因此任务拆解为,先遍历 A
中的每个节点(isSubStructure
),再判断树 A 中
以该节点为根节点的子树是否包含树 B(recursion
)。
1 | class Solution: |
二叉树的镜像
将右节点递归的返回值作为左节点,左节点递归的返回值作为右节点
1
2
3
4
5
6class 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
10class 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 | class Solution: |