leetcode题记:Same Tree-蒲公英云

leetcode题记:Same Tree

港控/mmm° 2022-05-18 05:57 250阅读 0赞

编程语言：JAVA

题目描述：

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

提交反馈：

57 / 57 test cases passed.
Status: Accepted
Runtime: 3 ms
Submitted: 3 minutes ago
You are here! 
Your runtime beats 98.53 % of java submissions.

解题思路：

最开始的想法是遍历二叉树，然后存入StringBuffer中，比较两个字符串是否相同。
 百度参考大神博客之后，发现这样的办法虽然也可以完成，但是太笨了。
直接用递归方法，结束条件为两颗树都为空或者其中一颗为空或者p.val不等于q.val;

代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        if(p.val!=q.val)
            return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}