剑指offer 判断树是不是对称的<?xml version="1.0" encoding="UTF-8"?>

递归是很常见的实现方式，最简便。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/* struct TreeNode {      int val;      struct TreeNode *left;      struct TreeNode *right;      TreeNode(int x) :              val(x), left(NULL), right(NULL) {      } }; */ class Solution { public :      bool isSymmetrical(TreeNode* pRoot)      {          if (!pRoot)  return true ;          return compRoot(pRoot -> left, pRoot -> right);      }      //递归方法      bool compRoot(TreeNode* lroot, TreeNode* rroot){          if (!lroot)  return (NULL == rroot);          if (NULL == rroot)  return false ;          if (lroot -> val != rroot -> val)  return false ;          return (compRoot(lroot -> left, rroot -> right) && compRoot(lroot -> right, rroot -> left));      }     };

---

迭代版本

使用栈stack

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

/* struct TreeNode {      int val;      struct TreeNode *left;      struct TreeNode *right;      TreeNode(int x) :              val(x), left(NULL), right(NULL) {      } }; */ class Solution { public :      bool isSymmetrical(TreeNode* pRoot)      {          if (pRoot==NULL) return true ;          stack<TreeNode *> s;          s.push(pRoot->left);          s.push(pRoot->right);          while (!s.empty()){              auto p=s.top();s.pop();              auto q=s.top();s.pop();              if (!p && !q) continue ; //p,q都是NULL，则继续              if (!p || !q) return false ; // p,q中有一个是null，另一个不是,false              if (p->val !=q->val) return false ; // p,q都不是null，但是值不相等，false                            s.push(p->left);              s.push(q->right);                            s.push(p->right);              s.push(q->left);                         }                 return true ;      } };