LeetCode小白菜笔记[22]：Same Tree

LeetCode小白菜笔记[22]：Same Tree

100. Same Tree [easy]

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          /        / 
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          /        / 
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

这道题就是判断两棵树相同与否，既要数值相同又要结构一样。code如下：

# 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 == None and q == None:
            return True
        elif p == None or q == None:
            return False
        else:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

递归实现，如果本节点相同且左右子树分别对应相同，那么就说明本节点为根的两棵树相同。前面的if用来解决特殊情况，即若两棵树都是空的，那么true，如果只有一个空树，false。先判断是为了防止p，q为空的情况下调用p.val，left，right出错。

测试通过，34ms，44.72%

2018年2月13日20:06:03