Python - 判断两树是否相同

给你两棵二叉树的根节点 p 和 q ，如果两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

判断两个树是否结构相同且数值相同，可以采用递归的方式同时遍历两棵树的根节点与左右节点，当结构不同或者结构相同值不同时退出，反之继续递归至最后一个节点。

#!/usr/bin/python
# -*- coding: UTF-8 -*-

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):

    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == q:
            return True
        try:
            if p.val == q.val:
                left = self.isSameTree(p.left, q.left)
                right = self.isSameTree(p.right, q.right)
                return left and right
        except:
            return False
        return False


s = Solution()
treeA = TreeNode(1)
treeA.left = 2
treeA.right = TreeNode(1)
treeB = TreeNode(1)
treeB.left = 2
treeB.right = TreeNode(1)
print(s.isSameTree(treeA, treeB))

上述方法采用了根-左-右的前序遍历方法，除此之外，也可以使用左-根-右的中序遍历方法、左右根的后序遍历方法，只要可以遍历树即可。

        try:
            if p.left.val == q.left.val:
                root = self.isSameTree(p, q)
                right = self.isSameTree(p.right, q.right)
                return root and right
        except:
            return False

        try:
            if p.right.val == q.right.val:
                root = self.isSameTree(p, q)
                left = self.isSameTree(p.left, q.left)
                return root and left
        except:
            return False

判断两树相同其实就是同时遍历两树即可，下面有树的几种常用用法可以参考~

DFS 相关: DFS 遍历树

BFS 相关:  BFS 遍历树

遍历根节点到叶节点路径: 获取树节点路径