当前位置:   article > 正文

代码随想录打卡第十五天

代码随想录打卡第十五天

代码随想录–二叉树部分

day15 二叉树第三天



一、力扣110–平衡二叉树

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

给定一个二叉树,判断它是否是 平衡二叉树

回顾定义:平衡二叉树指的是左右子树高度相差不大于1的树

用递归的方法做,那就是比较两个子树的最大深度,如果相差大于1,则返回-1告诉上层,这是不平衡树的节点,否则返回最大深度

代码如下:

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

        return max(leftDepth, rightDepth) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int Depth = getDepth(root);
        if(Depth == -1) return false;
        else return true;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

二、力扣257–二叉树的所有路径

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

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

这里就要用回溯了

回溯算法的想法类似于试错,一条路走到底发现错了,那就撤回几步,换另一条路走

所以本题也一样,先一条路走到底,得到一个路径后,返回上一个节点,走另一个子树,如果没有子树了,就再回去一格,重复下去

所以递归法的话,应该是传入当前树的根节点,而且有一个数组可以存这条路遍历过来的节点值

如果这个节点是叶节点,那就可以从数组中取数字出来做答案,存在result中,接着回溯

代码如下:

class Solution {
public:
    void traversal(TreeNode* curr, vector<int>& path, vector<string>& result)
    {
        if(!curr->left && !curr->right)
        {
            string temp;
            for(auto ele : path)
            {
                temp += to_string(ele);
                temp += "->";
            }
            temp += to_string(curr->val);
            result.push_back(temp);
        }
        if(curr->left)
        {
            path.push_back(curr->val);
            traversal(curr->left, path, result);
            path.pop_back();
        }
        if(curr->right)
        {
            path.push_back(curr->val);
            traversal(curr->right, path, result);
            path.pop_back();            
        }

    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(!root) return {};
        traversal(root, path, result);

        return result;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

回溯算法体现在path的push和pop,push+递归可以理解为向下试错,试错结束后pop就能体现出回溯的效果

三、力扣404–左叶子之和

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

给定二叉树的根节点 root ,返回所有左叶子之和。

第一反应用层序遍历秒了,但是层序遍历没法判断当前节点是不是左叶子节点,只能判断它是这层最左边的点

实际上需要通过父节点来判断当前节点是不是左叶子节点

所以传入父节点,检查其左节点不为空且左节点的左右节点为空,那么这个父节点就有一个左叶子节点,加进去就行

代码如下:

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        int sum = 0;
        sum += sumOfLeftLeaves(root->left);
        if(root->left && !root->left->left && !root->left->right)
        {
            sum += root->left->val;
        }
        sum += sumOfLeftLeaves(root->right);
        return sum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

四、力扣222–完全二叉树的节点个数

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

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

这个真的是层序遍历秒了

代码如下:

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode *> que;
        que.push(root);
        int result = 0;
        while(!que.empty())
        {
            int length = que.size();
            for(int i = 0; i < length ; i ++)
            {
                result ++;
                TreeNode * curr = que.front(); que.pop();
                if(curr->left) que.push(curr->left);
                if(curr->right) que.push(curr->right);
                /*Add function here*/
            }
        }
        return result; 
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

模板参考链接:层序遍历

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/792566
推荐阅读
相关标签
  

闽ICP备14008679号