LeetCode 3, 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.

cover-image
分析

既然要判断两棵树是不是完全相同，题目里已经说明了，不光节点的值要相同，而且形态也要一样，就是说节点的左右子树也要保持一样的深度。

我一开始想的是能不能使用在第一个练习里面实现过的maxDepth来判断左右子树的最大深度是否一致，进而能够将形态的判断完成然后再去看value的值是否一样。但这样一来，就需要两个递归函数了，应该还有比这个更简单的解法。

反过来想想isSameTree已经打算是一个递归函数了，那么能不能把这两个功能整合进一个里面去呢，答案显然是肯定的了。我们在isSameTree(BinaryTree *T1, BinaryTree *T2)里面就能够完成所有的判断，这个函数做这么几件事情：

  • 判断T1和T2是否全部为空，如果为空说明是两个空节点，那么它们是相等的，返回true
  • 如果T1或者T2其中有一个为空，另外一个不为空，那么他们就是不等的，直接返回false
  • 走到这里，说明对节点本身最基本的形态已经判断完成了，那么就可以看看value是否一致了，如果T1和T2的value一致，就可以递归去判断这两个节点的子树了，否则的话直接返回false

是不是很简单呢，这些问题都是上学的时候学习过的，但时间久了就忘记了，这道题目主要卡在对于递归出口条件的定位和使用，所以一开始能想到用递归左右子树，但是不知道怎么写出口条件。对递归的理解还是不够深入。

最后Accept的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for binary tree
 * 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 == NULL && q == NULL) 
            return true;
        if ((q == NULL && p != NULL) || (p == NULL && q != NULL)) 
            return false; 
        if (p->val == q->val) {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
        return false;
    }
};

这里面还犯了一个毛病就是一开始写成这样了

return isSameTree(p->left, q->left) == isSameTree(p->right, q->right) == true;

真是太大意了。