首页 > 代码库 > Symmetric Tree

Symmetric Tree

2024-07-18 01:51:06   218人阅读

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.

思路：对二叉树进行遍历即可。递归解法：使用CheckChild( left, right )判断两颗树left和right是否对称，对称条件为：二者都为空，或都不空且left->val==right->val、CheckChild( left->left, right->right ) && CheckChild( left->right, right->left )为真。（即left的左子树、右子树分别与right的右子树、左子树对称）

 1 class Solution { 2 public: 3     bool isSymmetric( TreeNode *root ) { 4         if( !root ) { return true; } 5         return CheckChild( root->left, root->right ); 6     } 7 private: 8     bool CheckChild( TreeNode*& left, TreeNode*& right ) { 9         if( !left && !right ) { return true; }10         if( left && right ) {11             if( left->val != right->val ) { return false; }12             return CheckChild( left->left, right->right ) && CheckChild( left->right, right->left );13         }14         return false;15     }16 };

使用迭代实现上述递归过程：

 1 class Solution { 2 public: 3     bool isSymmetric( TreeNode *root ) { 4         if( !root ) { return true; } 5         queue<TreeNode*> left, right; 6         left.push( root->left ); right.push( root->right ); 7         while( !left.empty() ) { 8             TreeNode *curLeft = left.front(), *curRight = right.front(); 9             left.pop(); right.pop();10             if( !curLeft && !curRight ) { continue; }11             if( curLeft && curRight && curLeft->val == curRight->val ) {12                 left.push( curLeft->left ); left.push( curLeft->right );13                 right.push( curRight->right ); right.push( curRight->left );14                 continue;15             }16             return false;17         }18         return true;19     }20 };

 


联系
我们