Leetcode-100 —— Same Tree

Description

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:

1
2
3
4
5
6
7
Input:     1         1
/ \ / \
2 3 2 3

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

Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
/ \
2 2

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

Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
/ \ / \
2 1 1 2

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

Output: false

分析

处理树的问题一般都离不开递归的思想,我们先把问题分解为两个子问题,

  1. 根节点相等
  2. 两颗树的左子树和右子树分别相等

程序设计

基于以上分析不难写出代码,如下,

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; }
* }
*/
class Solution {
public boolean 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);
}
}

哈哈,提交后一遍过了,写了这么久终于实现了第一次 bugfree,值得纪念。

本文标题:Leetcode-100 —— Same Tree

文章作者:Syncher

发布时间:2019年07月10日 - 11:07

最后更新:2019年07月10日 - 06:07

原始链接:https://0x400.com/2019-07-10-lc-100-same-tree.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。