leetcode 101. Symmetric Tree BFS广度优先遍历+DFS深度优先遍历-蒲公英云

leetcode 101. Symmetric Tree BFS广度优先遍历+DFS深度优先遍历

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.

这道题是判断二叉树是否对称，我这里使用的BFS广度优先遍历来做的。

代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 /*class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }
*/
public class Solution 
{
    public boolean isSymmetric(TreeNode root) 
    {
        if(root==null)
            return true;   
        Queue<TreeNode> myQueue = new LinkedList<>();
        myQueue.add(root);
        while(myQueue.isEmpty()==false)
        {
            int size=myQueue.size();
            List<Integer> list=new ArrayList<Integer>();
            for(int i=0;i<size;i++)
            {
                //如果当前的结点是null，仍然要添加为null，然后判断每一层的val是否是一个回文序列
                TreeNode tmp=myQueue.peek();
                if(tmp != null)
                {
                    myQueue.add(tmp.left);
                    myQueue.add(tmp.right);
                    list.add(tmp.val);
                }else
                    list.add(null);
                myQueue.poll();
            }
            if(checkSymmetric(list)==false)
                return false;
        }
        return true;
    }
    //检查list是否对回文序列（这个是包含null）
    private boolean checkSymmetric(List<Integer> list) 
    {
        if(list.size()<=0)
            return true;
        else
        {
            int left=0;
            int right=list.size()-1;
            while(left < right)
            {
                Integer l=list.get(left);
                Integer r=list.get(right);
                if(l==null && r==null || l!=null && r!=null && l==r)
                {
                    left++;
                    right--;
                }
                else
                    return false;
            }
            return true;
        }
    }
}

下面是C++的做法，就是一个简单的BFS广度优先遍历的做法

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
/*
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution
{
public:
    bool isSymmetric(TreeNode* root)
    {
        if (root == NULL)
            return true;
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* left, TreeNode* right)
    {
        if (left == NULL && right != NULL || left != NULL && right == NULL)
            return false;
        else if (left == NULL&&right == NULL)
            return true;
        else if (left->val != right->val)
            return false;
        else
            return dfs(left->left, right->right) == true && dfs(left->right, right->left);
    }
    bool isSymmetricByBFS(TreeNode* root)
    {
        if (root == NULL)
            return true;
        queue<TreeNode*> que;
        que.push(root);
        while (que.empty() == false)
        {
            int size = que.size();
            vector<int> list;
            for (int i = 0; i < size; i++)
            {
                TreeNode* top = que.front();
                if (top != NULL)
                {
                    que.push(top->left);
                    que.push(top->right);
                    list.push_back(top->val);
                }
                else
                    list.push_back(NULL);
                que.pop();
            }
            if (isVaild(list) == false)
                return false;
        }
        return true;
    }
    bool isVaild(vector<int> v)
    {
        if (v.size() <= 1)
            return true;
        else
        {
            int i = 0, j = v.size() - 1;
            while (i < j)
            {
                if (v[i] != v[j])
                    return false;
                else
                {
                    i++;
                    j--;
                }
            }
            return true;
        }
    }
};