题目描述
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
题目解答
递归比较的思想:
- 树对称的条件为——根的左子树的值和右子树的值成镜像
- 所以可以采取两个递归线路的方法,左子树的左节点值与右子树的右节点值必较;同样,左子树的右节点值与右子树的左节点值必较。若是全部相等,则说明该树对称
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSame(struct TreeNode* left, struct TreeNode* right) {
if (left == NULL && right == NULL)
return true;
else if (left == NULL || right == NULL)
return false;
else if (left->val != right->val)
return false;
else
return isSame(left->left, right->right) &&
isSame(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root) {
if (root == NULL)
return true;
return isSame(root->left, root->right);
}