100. Same Tree

  • 45.6%

https://leetcode.com/problems/same-tree/

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

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


方法一:

https://discuss.leetcode.com/topic/5972/here-s-a-c-recursion-solution-in-minimal-lines-of-code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//
// Algorithm for the recursion:
// 1)
// If one of the node is NULL then return the equality result of p an q.
// This boils down to if both are NULL then return true,
// but if one of them is NULL but not the other one then return false
// 2)
// At this point both root nodes represent valid pointers.
// Return true if the root nodes have same value and
// the left tree of the roots are same (recursion)
// and the right tree of the roots are same (recursion).
// Otherwise return false.
//

bool isSameTree(TreeNode *p, TreeNode *q) {
if (p == NULL || q == NULL) return (p == q);
return (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
}

我的代码实现:

1
2
3
4
5
6
7
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL && q==NULL) return true;
return p!=NULL && q!=NULL && p->val==q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
if(!p || !q) return false;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};

python


https://discuss.leetcode.com/topic/14561/shortest-simplest-python

The “proper” way:

1
2
3
4
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p is q

The “tupleify” way:

1
2
3
4
def isSameTree(self, p, q):
def t(n):
return n and (n.val, t(n.left), t(n.right))
return t(p) == t(q)

The first way as one-liner:

1
2
def isSameTree(self, p, q):
return p and q and p.val == q.val and all(map(self.isSameTree, (p.left, p.right), (q.left, q.right))) or p is q

https://discuss.leetcode.com/topic/18353/python-recursive-solution-and-dfs-iterative-solution-with-stack-and-bfs-iterative-solution-with-queue

Python Recursive solution and DFS Iterative solution with stack and BFS Iterative solution with queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def isSameTree1(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return p == q

# DFS with stack
def isSameTree2(self, p, q):
stack = [(p, q)]
while stack:
node1, node2 = stack.pop()
if not node1 and not node2:
continue
elif None in [node1, node2]:
return False
else:
if node1.val != node2.val:
return False
stack.append((node1.right, node2.right))
stack.append((node1.left, node2.left))
return True

# BFS with queue
def isSameTree3(self, p, q):
queue = [(p, q)]
while queue:
node1, node2 = queue.pop(0)
if not node1 and not node2:
continue
elif None in [node1, node2]:
return False
else:
if node1.val != node2.val:
return False
queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))
return True

my code

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if not p and not q:
return True
return p!=None and q!=None and (p.val==q.val) and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

其中 p!=None and q!=None,这一段,如果换成p and q,则结果不是false,而是null。


java


https://discuss.leetcode.com/topic/4737/five-line-java-solution-with-recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public 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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
return false;
}
}

https://discuss.leetcode.com/topic/9739/2-lines-java-code


1
2
3
4
5
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
return p != null && q != null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
} }

谢谢你,可爱的朋友。