【Leetcode】【Easy】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:

But the following is not:

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

递归的解法：

新建一个递归调用自身的函数，输入是待比较的左结点和右结点，输出是对称判定结果：true or false；

 class Solution {

 public:

     bool isSymmetric(TreeNode *root) {

         if (!root)

             return true;

         return isSame(root->left, root->right);

     }

     bool isSame(TreeNode *node_l, TreeNode *node_r){

         if (!node_l && !node_r)

             return true;

         if (!node_l || !node_r)

             return false;

         if (node_l->val != node_r->val){

             return false;

         }

         return isSame(node_l->left, node_r->right) && \

         　　　　isSame(node_l->right, node_r->left);

     }

 };

迭代的解法：

新建两个栈用于存放待比较的左子树结点和右子树结点。每次迭代拿出两个栈中同位置元素进行比较，结束后删除此比较过的元素，并将其左右儿子压栈待比较。（还有只用一个栈的方法，并没有节省空间，略）

 class Solution {

 public:

     bool isSymmetric(TreeNode *root) {

         if (!root)

             return true;

         stack<TreeNode *> leftNodeStack;

         stack<TreeNode *> rightNodeStack;

         leftNodeStack.push(root->left);

         rightNodeStack.push(root->right);

         TreeNode *leftNode;

         TreeNode *rightNode;

         while (!leftNodeStack.empty()) {

             leftNode = leftNodeStack.top();

             rightNode = rightNodeStack.top();

             leftNodeStack.pop();

             rightNodeStack.pop();

             if (!leftNode && !rightNode) {

                 continue;

             }

             if ((!leftNode && rightNode) || \

             (leftNode && !rightNode)) {

                 return false;

             }

             if (leftNode->val != rightNode->val) {

                 return false;

             }

             leftNodeStack.push(leftNode->left);

             leftNodeStack.push(leftNode->right);

             rightNodeStack.push(rightNode->right); // Notice

             rightNodeStack.push(rightNode->left);

         }

         return true;

     }

 };

巴特西

【Leetcode】【Easy】Symmetric Tree

最新文章

热门文章