JZ28-题解 | #对称的二叉树#
对称的二叉树
http://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb
题目描述
给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)
** 题解:递归**
注意:
1、对于需要比较节点中的值的时候,需要提前判断节点是否为空;
2、如果不需要比较节点的值,那么递归调用时候不需要提前判断节点是否为空;
3、如果是需要有两个节点进行比较,那么需要创建一个递归函数;
递归函数中,通常先进性比较,然后分别进行左子树和右子树的递归
4、如果不需要两个节点进行比较,不需要重新创建递归函数,以本函数作为递归函数。
代码
/*
描述
给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)
*/
/*
题解1:递归
注意:
1、对于需要比较节点中的值的时候,需要提前判断节点是否为空;
2、如果不需要比较节点的值,那么递归调用时候不需要提前判断节点是否为空;
3、如果是需要有两个节点进行比较,那么需要创建一个递归函数;
递归函数中,通常先进性比较,然后分别进行左子树和右子树的递归
4、如果不需要两个节点进行比较,不需要重新创建递归函数,以本函数作为递归函数。
*/
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
//递归出口
if (!pRoot1 && !pRoot2) //两个节点都为空时,返回真
return true;
if (!pRoot1 || !pRoot2)//两个节点都存在空节点时,返回假
return false;
//if(pRoot1->val ==pRoot2->val){
// return isSame(pRoot1->left,pRoot2->right) &&
// isSame(pRoot1->right,pRoot2->left);
//}else
// return false;
//上面几行加了注释的代码也可以用下面几行代码表示
if (pRoot1->val != pRoot2->val) return false;
if (isSame(pRoot1->left, pRoot2->right) && isSame(pRoot1->right, pRoot2->left))
return true;
return false;
}
bool isSymmetrical(TreeNode* pRoot) {
if (!pRoot)
return true;
return isSame(pRoot->left, pRoot->right);
//注意:这里不能再此处进行自我递归,因为形参只有一个
//若自我递归,得到的是子树左右结点的比较,而不是左子树的左节点和右子树的右节点比较。
//所以只能再递归函数中进行递归。
}