首页 > 编程语言 > 详细

C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]

时间:2022-05-27 21:45:04      阅读:14      评论:0      收藏:0      [点我收藏+]

题目:

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

例如,二叉树 [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

链接:https://leetcode-cn.com/problems/symmetric-tree

最开始的思路是用层次遍历,每一行看看是不是回文数组,但后来发现例如样例2那样的树就会判断错误,递归也没想好怎么个调用思路。

 

正确的递归思路:来源:https://leetcode-cn.com/u/haventmetyou-2/

1.怎么判断一棵树是不是对称二叉树? 答案:如果所给根节点,为空,那么是对称。如果不为空的话,当他的左子树与右子树对称时,他对称

2.那么怎么知道左子树与右子树对不对称呢?在这我直接叫为左树和右树 答案:如果左树的左孩子与右树的右孩子对称,左树的右孩子与右树的左孩子对称,那么这个左树和右树就对称。

仔细读这句话,是不是有点绕?怎么感觉有一个功能A我想实现,但我去实现A的时候又要用到A实现后的功能呢?

当你思考到这里的时候,递归点已经出现了: 递归点:我在尝试判断左树与右树对称的条件时,发现其跟两树的孩子的对称情况有关系。

想到这里,你不必有太多疑问,上手去按思路写代码,函数A(左树,右树)功能是返回是否对称

def 函数A(左树,右树): 左树节点值等于右树节点值 且 函数A(左树的左子树,右树的右子树),函数A(左树的右子树,右树的左子树)均为真 才返回真

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSame(root,root);
    }
    bool isSame(TreeNode* q,TreeNode *p)
    {
        if(q==nullptr&&p==nullptr) return true;
        else if(q&&!p||!q&&p) return false;
        else if(q->val==p->val)
        {
            return isSame(q->left,p->right)&&isSame(q->right,p->left);
        }
        return false;
    }
};

非递归思路与层次遍历类似,只不过改成每次比较当前两结点的最左和最右得结点值是否相等:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        queue<TreeNode * > vec;
        vec.push(root->left);
        vec.push(root->right);
        while(vec.size()!=0)
        {
            TreeNode * a=vec.front();
            vec.pop();
            TreeNode * b=vec.front();
            vec.pop();
            if(!a&&!b) //两个都是是空则认为为真
            {
                continue;
            }
            else if(a==nullptr||b==nullptr||a->val!=b->val)//有一个不是空或者都不是空而且数值不一样,则为假,直接返回
                return false;
            vec.push(a->left);//这四句代码其实就是递归的顺序
            vec.push(b->right);
            vec.push(a->right);
            vec.push(b->left);
        }
        return true;
    }
    
};

可以发现非递归做法是把递归思路放到循环里了

C++ 判断对称二叉树的递归和非递归做法 [LeetCode 101]

原文:https://www.cnblogs.com/murenma/p/15337639.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!