欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode101——对称二叉树——c++版本实现

程序员文章站 2022-05-20 13:49:43
...

 

题面来啦~

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

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

class Solution {
public:

bool isSymmetric(TreeNode* root) {

    }
};

如果还没有看我的前一篇Leetcode100的朋友请先去看那篇哦~ 强烈建议先100后101,101这道题可以有效检验你是否学会了如100这种二叉树的递归操作思想! 

如果看过了100的话,我们就开始讲解啦~

其实思路很简单,根据镜像的定义,不过是在遍历的时候设置两个指针,一个向左一个向右同时遍历,并逐步比对。

但我们发现这道题的函数只有根节点,那带一个双参的子函数就可以完美解决啦~ 下面给出代码哦

要注意的是,根节点的子节点情况我选择在原始函数中给出判断,这样方便子函数安安心心的往下遍历~

class Solution {
public:
    bool search(TreeNode* r1,TreeNode* r2)
    {
        if(r1&&r2)
        return r1->val==r2->val&&search(r1->left,r2->right)&&search(r1->right,r2->left);
        
        else if((r1&&!r2)||(!r1&&r2))
            return false;
        else return true;
    }
    
    bool isSymmetric(TreeNode* root) {
        
        if(!root)
            return true;
        if(!root->left&&!root->right)
            return true;

        return search(root->left,root->right);
        
    }
};

下面给大家带来迭代的方法,下面的方法分别是基础的队列、栈的应用~   原理很简单,上机熟悉就好 

首先是queue 队列的方法,主要的函数为 front() empty() pop() push()

class Solution {
public:
    
    bool isSymmetric(TreeNode* root) {
        
        
        if(!root)
            return true;
    
        //左树
        TreeNode *p1 = root;
        //右树
        TreeNode *p2 = root;
      
        if(!p1->left&&!p1->right)
            return true;
        
        queue<TreeNode *> left,right;
        left.push(p1->left);
        right.push(p2->right);
        
        while(!left.empty()&&!right.empty())
        {
            p1 = left.front();
            left.pop();
            p2 = right.front();
            right.pop();
            
           
            
            if(!p1&&!p2)
                continue;
             else if(!p1||!p2)
                return false;
            else if(p1->val!=p2->val)
                return false;
            
            left.push(p1->left);
            left.push(p1->right);
            right.push(p2->right);
            right.push(p2->left);
        }
        
        return true;
    }
};