leetcode_101.对称二叉树(递归思路)

题目

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

1
/ \
2 2
/ \ / \
3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
/ \
2 2
\ \
3 3

说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

思路

1.首先弄清楚“对称”一词的含义,首先我们知道,一棵如题所述的镜像对称二叉树,从根结点出发,应该是——如下图标同颜色的节点一般,对应的节点的值相等。

1-1
2.现在开始考虑写递归函数,看着上图假设,我们应该怎样才能设计一个递归函数,可以从根节点开始,向两边扩展,同步到达No.1,No.2,No.3这样的一组组节点呢?
请注意,以上的这段话实则已经点明了递归函数的几个要点。

1.基于根节点。
2.是同时向两边扩展的。
3.同步到达像No.1,No.2,No.3这样的一组组节点。

显而易见,只要我们保证从根节点开始,左右子树同时行动,并遵循一定的规律,满足第三点就是顺理成章的事情了。(可能有点难以理解,看下去就懂了)

前方高能

那么,如何保证从根节点开始,左右子树同时行动,并遵循一定的规律

显然,如果要保证左右子树同时行动,该递归函数应该要有两个指针,like this:

class Solution {
public:
bool isSymmetric(TreeNode* root) {
return digit(root -> right, root -> left);
}
private:
bool digit(TreeNode* a, TreeNode* b) {
^^^^^^^^^^^^^^^^^^^^^^^^快看,两个指针!
}
};

我们再假设根节点的深度为0,以下逐层+1,如下图所示:

1-2
现在思考,如果我们已经确保,两个指针已经分别指向了相同颜色的两个节点,那么下一步应该如何行动,才能确保它们依旧指向相同颜色的两个节点呢?

很简单,“如果一个指针向左子树移动,则另一个向右子树移动;如果向右子树移动,则另一个向左子树移动。”总而言之,两个指针的移动方向应该是相反的,并且都是向深度+1 的方向移动,才能确保它们依旧指向同一组。

请仔细阅读这段话,它体现了总体的思路:

从根节点出发,两个指针分别向左、右子树移动,遵循左右方向相反,向下直到叶子节点为止的原则,同时比对指针所指向的点的数值是否相等,如果不相等或者其中一个指针无路可走,则返回false,如果一直安然无恙直到两个指针同时走到尽头,就可以返回true

以下是代码:

/**
* 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 isSymmetric(TreeNode* root) {
return digit(root -> right, root -> left); //根节点的左右子树
}
private:
bool digit(TreeNode* a, TreeNode* b) {
if(a == NULL && b == NULL) return true; //两个都走到尽头,true
else if(a == NULL || b == NULL) return false; //只有一个走到尽头,false
else
return a -> val == b -> val &&
digit(a -> left, b -> right) &&
digit(a -> right, b -> left); //否则对比数值,继续递归
}
};

但是,这样还是错误,为什么呢?

呵呵,我们还需要加上一条语句,判断树是否为空。

这是最后的双100%代码:

/**
* 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 isSymmetric(TreeNode* root) {
if(root == NULL) return true; //判断树是否为空
return digit(root -> right, root -> left); //根节点的左右子树
}
private:
bool digit(TreeNode* a, TreeNode* b) {
if(a == NULL && b == NULL) return true; //两个都走到尽头,true
else if(a == NULL || b == NULL) return false; //只有一个走到尽头,false
else
return a -> val == b -> val &&
digit(a -> left, b -> right) &&
digit(a -> right, b -> left); //否则对比数值,继续递归
}
};


作者:cgz2006

相关推荐

Django cookie 与 session

Django cookie 与 session

使用VSCode开发和调试.NET Core程序的方法

使用VSCode开发和调试.NET Core程序的方法

flexible.js实现移动端rem适配方案

IdentityServer4 QuckStart 授权与自定义Claims的问题