[剑指offer] 58. 对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

---

思路： 比较是否对称，即： 比较当前节点的 左节点 = 右节点 　　　　　　　  左子树的左子树 = 右子树的右子树 　　　　　　　 左子树的右子树 = 右子树的左子树 非递归实现 class Solution { public: bool isSymmetrical(TreeNode *pRoot) { if (pRoot == NULL) return true; queue<TreeNode *> qL, qR; qL.push(pRoot->left); qR.push(pRoot->right); TreeNode *left, *right; while (!qL.empty() && !qR.empty()) { left = qL.front(); qL.pop(); right = qR.front(); qR.pop(); if (left == NULL && right == NULL) continue; if (left == NULL || right == NULL) return false; if (left->val != right->val) return false; qL.push(left->left); qL.push(left->right); qR.push(right->right); qR.push(right->left); } return true; } };

递归实现:

class Solution { public: bool isSymmetrical(TreeNode *pRoot) { if (pRoot == NULL) return true; return isSymmetrical(pRoot->left, pRoot->right); } bool isSymmetrical(TreeNode *LR, TreeNode *RR) { if (LR == NULL && RR == NULL) return true; if (LR == NULL || RR == NULL) return false; if (LR->val != RR->val) return false; return isSymmetrical(LR->left, RR->right) && isSymmetrical(LR->right, RR->left); } };

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10244370.html