首页 > 代码库 > LeetCode: Symmetric Tree

LeetCode: Symmetric Tree

2024-07-20 01:47:11   225人阅读

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.

地址：https://oj.leetcode.com/problems/symmetric-tree/

算法：写了一个非递归的算法。用BFS遍历，每到一层结束判断该层节点是否对称，其中对于空的节点用0X80000000表示。代码：

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isSymmetric(TreeNode *root) {13         if(!root)   return true;14         queue<TreeNode *> que;15         int num_push = 0;16         int num_pop  = 0;17         int last     = 1;18         que.push(root);19         ++num_push;20         vector<int> temp;21         while(!que.empty()){22             TreeNode *node_pop = que.front();23             if(node_pop){24                 temp.push_back(node_pop->val);25                 que.push(node_pop->left);26                 ++num_push;27                 que.push(node_pop->right);28                 ++num_push;29             }30             else31                 temp.push_back(0x80000000);32             que.pop();33             ++num_pop;34             if(num_pop == last){35                 int i = 0;36                 while(i < temp.size()/2 && temp[i] == temp[temp.size()-i-1])    ++i;37                 if(i < temp.size()/2)   return false;38                 last = num_push;39                 temp.clear();40             }41         }42         return true;43     }44     45 };

 

LeetCode: Symmetric Tree


联系
我们