LeetCode--Symmetric Tree

首页 > 代码库 > LeetCode--Symmetric Tree

2024-07-04 21:50:58 222人阅读

对于本题，想到一个中序遍历后，判别是否为回文串的方法，却WA多次

class Solution {
public:
    vector<int> vectorValue;
    void inOrder(TreeNode* root)
    {
        if(root!=NULL)
        {
            inOrder(root->left);
            vectorValue.push_back(root->val);
            inOrder(root->right);
        }
    }

    bool isSymmetric(TreeNode *root) {
        
        if(root==NULL)return true;
        vectorValue.clear();
        inOrder(root);
        int length=vectorValue.size();
        for(int i=0;i<length/2;i++)
        {
            if(vectorValue[i]!=vectorValue[length-1-i])
                return false;
        }
        return true;
    }
};

后来，查了资料才知道－－产生错误的原因：回文串丢失了层次，位置信息。参考别人方法

一种笨方法解决了这个问题，那便是逐层检查逐层扩展，检查每一层的节点是否互相对称。

[java] view plaincopyprint?

import java.util.ArrayList;
import java.util.List;
public class Solution {
class ExtTreeNode {
TreeNode node;
long pos;
ExtTreeNode(TreeNode node, long pos) {
this.node = node;
this.pos = pos;
}
}
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
List<ExtTreeNode> lNodes, rNodes, lTempNodes, rTempNodes;
lNodes = new ArrayList<ExtTreeNode>();
rNodes = new ArrayList<ExtTreeNode>();
if (root.left != null) {
lNodes.add(new ExtTreeNode(root.left, 1));
}
if (root.right != null) {
rNodes.add(new ExtTreeNode(root.right, 2));
}
int count = 2;
while (lNodes.size() > 0) {
if (rNodes.size() == 0 || rNodes.size() != lNodes.size()) {
return false;
}
lTempNodes = new ArrayList<ExtTreeNode>();
rTempNodes = new ArrayList<ExtTreeNode>();
for (int i = 0; i < lNodes.size(); i++) {
ExtTreeNode lNode = lNodes.get(i);
ExtTreeNode rNode = rNodes.get(i);
if (lNode.pos + rNode.pos != count + 1 || lNode.node.val != rNode.node.val) {
return false;
}
if (lNode.node.left != null) {
lTempNodes.add(new ExtTreeNode(lNode.node.left, lNode.pos * 2 - 1));
}
if (lNode.node.right != null) {
lTempNodes.add(new ExtTreeNode(lNode.node.right, lNode.pos * 2));
}
if (rNode.node.right != null) {
rTempNodes.add(new ExtTreeNode(rNode.node.right, rNode.pos * 2));
}
if (rNode.node.left != null) {
rTempNodes.add(new ExtTreeNode(rNode.node.left, rNode.pos * 2 - 1));
}
}
lNodes = lTempNodes;
rNodes = rTempNodes;
count *= 2;
}
return rNodes.size() == 0;
}
}

附自己调试代码主要参与了http://blog.csdn.net/greenapple_shan/article/details/25976165

/*
* LeetCode--Symmetric Tree
* date 2014/5/16
* state AC
*/
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

/**
 * Definition for binary tree
 */
 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	/*
    vector<int> vectorValue;
    void inOrder(TreeNode* root)
    {
        if(root!=NULL)
        {
            inOrder(root->left);
            vectorValue.push_back(root->val);
            inOrder(root->right);
        }
    }

    bool isSymmetric(TreeNode *root) {
        
        if(root==NULL)return true;
        vectorValue.clear();
        inOrder(root);
        int length=vectorValue.size();
        for(int i=0;i<length/2;i++)
        {
            if(vectorValue[i]!=vectorValue[length-1-i])
                return false;
        }
        return true;
    }
	
	bool isSymRec(TreeNode* left,TreeNode* right)
	{
		//递归结束条件
		if(left==NULL && right==NULL)
			return true;
		else if(left==NULL || right==NULL)
			return false;
		//递归体
		return(left->val == right->val //结点数值比较
			&& isSymRec(left->left,right->right) //左子树左对右子树右
			&& isSymRec(left->right,right->left));//左子树右对右子树左
	}
	bool isSymmetric(TreeNode* root)
	{
		if(root==NULL)return true;
		else isSymRec(root->left,root->right);
	}
	*/
	bool isSymmetric(TreeNode *root) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if(root==nullptr) return true;  
        queue<TreeNode*> q1;  
        queue<TreeNode*> q2;  
          
        q1.push(root->left);  
        q2.push(root->right);  
          
        while( !q1.empty() || !q2.empty()) {  
            TreeNode* t1 = q1.front();  
            TreeNode* t2 = q2.front();  
            q1.pop();  
            q2.pop();  
              
            if(t1==nullptr && t2==nullptr) continue;  
            if(t1==nullptr || t2==nullptr) return false;  
              
            if(t1->val!=t2->val) return false;  
             
            q1.push(t1->left);  
            q1.push(t1->right);  
            q2.push(t2->right);  
            q2.push(t2->left);  
        }  
          
        return true;  
          
    }    
};

TreeNode* create()
{
    char ch;
    cin>>ch;
    TreeNode* root;
    if(ch==‘#‘)
        return NULL;
    else
    {
        root=new TreeNode(ch);
        root->left=create();
        root->right=create();
        return root;
    }
}

bool isSame(vector<int>& vectorValue)
{
	int length=vectorValue.size();
    for(int i=0;i<length;i++)
    {
        if(vectorValue[i]!=vectorValue[length-1-i])
           return false;
    }
}

int main()
{
    //cout << "Hello world!" << endl;
	
    TreeNode* t;
    t=create();
    Solution Solu;
	Solu.inOrder(t);
	int len=Solu.vectorValue.size();
	for(int i=0;i<len;i++)
		//cout<<Solu.vectorValue[i]<<" ";
			printf("%c ",Solu.vectorValue[i]);
	cout<<endl;
    if(Solu.isSymmetric(t))
        cout<<"true"<<endl;
    else cout<<"false"<<endl;
	
	/*
	vector<int> vec;
	int n;
	cin>>n;
	int t;
	for(int i=0;i<n;i++)
	{
		cin>>t;
		vec.push_back(t);
	}
	if(isSame(vec))cout<<"true"<<endl;
	else cout<<"false"<<endl;
	*/
    return 0;
}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > LeetCode--Symmetric Tree

LeetCode--Symmetric Tree

看完仍有疑问？有类似问题直接问程序猿