[LeetCode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

1. 递归解法：

这题看着很tricky，实际上本质思路算法和Same Tree那题换汤不换药。让我们来比较下两题。

T(p)和T(q)是same tree的条件：

(1) p和q等价（同时为NULL，或同时不为NULL且val相同）

(2) T(p->left)和T(q->left)为same tree，且T(p->right)和T(q->right)为same tree。

T(r)是symmetric的条件：实际就是判断T(r->left)和T(r-right)是否互为镜像的问题。假设p和q分别指向同一个tree内部两个镜像对称的节点，例如题目例子中的两个节点2

(1) p和q等价（同时为NULL，或同时不为NULL且val相同）

(2) T(p->left)和T(q->right)必须互为镜像，且T(p->right)和T(q->left)必须互为镜像。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: bool isSymmetric(TreeNode *root) { return isSym(root, root); } bool isSym(TreeNode *lr, TreeNode *rr) { if(!lr && !rr) return true; if((!lr && rr) || (lr && !rr)) return false; if(lr==rr) return isSym(lr->left, lr->right); // lr and rr both point to root if(lr->val != rr->val) return false; return isSym(lr->left, rr->right) && isSym(lr->right, rr->left); } };

总结：

ln 10有一个特殊处理，当lr和rr指向同一节点时，必然这个节点是整个树的root。此时避免重复判断，只要判断它的左和右子树是否互为镜像即可。


2. 迭代解法：

迭代解法本质上和递归解法是一回事，尽管理解上没有递归这么直观简洁。通常用stack或queue来暂时存放之后要处理的节点。这里由于要判断左右子树是否镜像，用两个queue分别对左右子树进行BFS的一层一层地访问。在访问中压入子节点到两个queue时，采用完全相反的顺序：对左子树先压入left child再right child；对右子树先压入right child再left child。这样一来将symmetric tree问题又转换为了same tree问题。

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

class Solution { public: bool isSymmetric(TreeNode *root) { if(!root) return true; queue<TreeNode*> ql, qr; ql.push(root->left); qr.push(root->right); while(!ql.empty() && !qr.empty()) { TreeNode *lnode = ql.front(); TreeNode *rnode = qr.front(); ql.pop(); qr.pop(); if(!lnode && !rnode) continue; if((!lnode && rnode) || (lnode && !rnode)) return false; if(lnode->val != rnode->val) return false; ql.push(lnode->left); qr.push(rnode->right); ql.push(lnode->right); qr.push(rnode->left); } if(!ql.empty() || !qr.empty()) return false; return true; } };

总结：

ln 15 -17对应了递归解法的ln 8, 9 , 11。除了用queue外，也可用两个stack进行左右镜像的dfs访问。