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

绝地灬酷狼 2022-06-08 02:14 262阅读 0赞

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;
            }
        }
    };