#! /usr/bin/env python
# coding: utf-8

'''
题目：相同的树 https://leetcode-cn.com/problems/same-tree/
主题：tree & depth-first search

解题思路：
1. 深度优先遍历，比较左右子树
'''


# Definition for a binary tree node.
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 and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        return p == q


if __name__ == '__main__':
    pass
