自己想的办法 非递归

思路

• 使用层次遍历，形成每层的遍历结果输出向量，对该向量经行回文检查，如果不满足就肯定不是对称树

• 在层次遍历过程中，扩展下一层节点时，加入二叉树左右子树的记录向量。判断是否满足一下两个条件：

• 向量长度是不是偶数

• 是不是兑成，左对应右，右对应左

几个点

• 一开始想的太简单了，认为回文字符串就足够了，但是没有考虑到树的结构不匹配。

• 这题目大概做了一个多小时吧，做的太慢了，还是做的题目太少了。

代码

/*

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

TreeNode(int x) :

val(x), left(NULL), right(NULL) {

}

};

*/

class Solution {

public:

bool isSymmetricalHelper(vector vec)

{

int i=0, j=vec.size()-1;

while(i<j)

{

if(vec[i]!=vec[j])

return false;

i++;

j--;

}

return true;

}

bool tree_LR_march(vector vec)

{

if(vec.size()%2)

return false;

int i=0, j=vec.size()-1;

while(i<j)

{

if((vec[i]+vec[j]) != 1) // L: 0 R: 1 左右对应

return false;

i++;

j--;

}

return true;

}

bool isSymmetrical(TreeNode* pRoot) {

if(!pRoot)

return true;

queue Q;

Q.push(pRoot);

//层次遍历一层一层来

while(!Q.empty())

{

queue Q_help;

vector vec;

vector RL_flag;

while(!Q.empty())

{

TreeNode* node = Q.front();

Q.pop();

vec.push_back(node->val);

if(node->left)

{

Q_help.push(node->left);

RL_flag.push_back(0);

}

if(node->right)

{

Q_help.push(node->right);

RL_flag.push_back(1);

}

}

if(!isSymmetricalHelper(vec) || !tree_LR_march(RL_flag))

return false;

Q = Q_help;

}

return true;

}

};

递归方法

传入做左子树和右子树，先确定使用那种遍历方式。深度优先遍历-先序遍历

几个点

• 递归实在是太神奇了，而且这种递归方式是不可能在回到一个子树上的，当初就是没想清楚这个点。

• 本质上就是一种递归遍历、枚举，一个节点生成两个节点

代码

/*

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

TreeNode(int x) :

val(x), left(NULL), right(NULL) {

}

};

*/

class Solution {

public:

bool dfs(TreeNode* L, TreeNode* R)

{

if(L==NULL && R==NULL)

return true;

if(L==NULL || R==NULL)

return false;

if(L->val != R->val)

return false;

return dfs(L->left, R->right) && dfs(L->right, R->left);

}

bool isSymmetrical(TreeNode* pRoot) {

if(!pRoot)

return true;

return dfs(pRoot->left, pRoot->right);

}

};