代码随想录打卡第十四天

代码随想录–二叉树部分

day14 二叉树第二天

文章目录

代码随想录--二叉树部分
一、力扣226--反转二叉树
二、力扣101--对称二叉树
三、力扣104--二叉树的最大深度
四、力扣111--二叉树的最小深度

一、力扣226–反转二叉树

代码随想录题目链接：代码随想录

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

递归法可以秒了

代码如下：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

二、力扣101–对称二叉树

代码随想录题目链接：代码随想录

给你一个二叉树的根节点 root ，检查它是否轴对称。

这道题用递归做的话，反而不太好写

因为要检查是否轴对称，所以其实迭代需要传入两颗树的root，比较两棵树是否对称

而仅在这两个root不为空且数字一样时，再进行下一步的检查

也就是递归检查左树的左节点和右树的右节点是否一样，以及左树的右节点和右树的左节点是否一样

代码如下：

class Solution {
public:
    bool checkThem(TreeNode * leftN, TreeNode * rightN)
    {
        if(leftN != nullptr && rightN == nullptr) return false;
        else if(leftN == nullptr && rightN != nullptr) return false;
        else if(leftN == nullptr && rightN == nullptr) return true;
        else if(leftN->val != rightN ->val) return false;

        bool outside = checkThem(leftN->left, rightN->right);
        bool inside = checkThem(leftN->right, rightN->left);
        return outside && inside;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return checkThem(root->left, root->right);
    }
};

用遍历法写就会简单的多，一层一层地把元素入队，每次出两个比较，都一样且队空就是对称，否则不对称

代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        queue<TreeNode*> checkQue;
        checkQue.push(root->left);
        checkQue.push(root->right);
        while(!checkQue.empty())
        {
            TreeNode * leftN = checkQue.front();
            checkQue.pop();
            TreeNode * rightN = checkQue.front();
            checkQue.pop();

            if(!leftN && !rightN) continue; // both nullptr
            else if(!leftN && rightN) return false;
            else if(leftN && !rightN) return false;
            else if(leftN->val != rightN->val) return false;

            checkQue.push(leftN->left);
            checkQue.push(rightN->right);
            checkQue.push(leftN->right);
            checkQue.push(rightN->left);
        }
        return true;
    }
};

附加题：力扣100–相同的树

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        else if(!p && q) return false;
        else if(!q && p) return false;
        else if(p->val != q->val) return false;

        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

力扣572–另一颗树的子树，层序遍历+相同树判断

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        else if(!p && q) return false;
        else if(!q && p) return false;
        else if(p->val != q->val) return false;

        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode * curr = que.front(); que.pop();
            if(isSameTree(curr, subRoot)) return true;
            if(curr->left) que.push(curr->left);
            if(curr->right) que.push(curr->right);
        }
        return false;
    }
};

三、力扣104–二叉树的最大深度

代码随想录题目链接：代码随想录

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

第一反应就是层序遍历，每次遍历+1即可

代码如下：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth = 0;
        if(!root) return depth;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            depth ++;
            for(int i = 0; i < length; i++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
            }
        }
        return depth;
    }
};

迭代法做也是可以的，迭代遍历左右树层数，选最大的那个，每层迭代向上返回时+1即可记录迭代层数

代码如下：

class Solution {
public:
    int getDepth(TreeNode * curr)
    {
        if(!curr) return 0;

        int leftDepth = getDepth(curr->left);
        int rightDepth = getDepth(curr->right);
        return 1+max(leftDepth, rightDepth);
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};

可以简洁，但是为了方便回忆，就这么写吧

附加题：力扣559–N叉树的最大深度

class Solution {
public:
    int maxDepth(Node* root) {
       if(!root) return 0; 
       int depth = 0;
       queue<Node *> que;
       que.push(root);
       while(!que.empty())
       {
            int length = que.size();
            depth ++;
            for(int i = 0; i < length; i ++)
            {
                Node * curr = que.front(); que.pop();
                for(auto child : curr->children)
                {
                    if(child) que.push(child);
                }
            }
       }
       return depth;
    }
};

或

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) return 0;
        int depth = 0;
        for(auto child : root->children)
        {
            int curr_depth = maxDepth(child);
            depth = depth > curr_depth ? depth : curr_depth;
        }
        return depth + 1;
    }
};

四、力扣111–二叉树的最小深度

代码随想录题目链接：代码随想录

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

跟最大深度不同的是，返回时需要检查一下这个节点是否有左右树，如果是单侧树的话，不能单纯返回1+min的结果

只有该节点左右树都有或者都没有的情况下才能返回1+min，因为此时的节点才有可能是叶子节点

代码如下：

class Solution {
public:
    int getDepth(TreeNode * curr)
    {
        if(!curr) return 0;
        
        int leftDepth = getDepth(curr->left);
        int rightDepth = getDepth(curr->right);

        if(!curr->left && curr->right) return 1 + rightDepth;
        if(!curr->right && curr->left) return 1 + leftDepth;

        return 1 + min(leftDepth, rightDepth);
    }
    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

迭代法：正常的层序遍历，但是在检查到第一个叶子节点的时候就return，下面的就不用遍历了

因为是一层一层的遍历，每次遍历都是同一层的叶子节点，也就无所谓是哪一个，深度是一样的

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int depth = 0;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty())
        {
            int length = que.size();
            depth ++;
            for(int i = 0; i < length; i ++)
            {
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                if(!curr->left && !curr->right) return depth;
            }
        }
        return depth;
    }
};