代码随想录算法训练营第十六天 | 110. 平衡二叉树、257. 二叉树的所有路径、404.左叶子之和

发布时间:2024年01月13日

题目链接:leetcode 110. 平衡二叉树

文章讲解:代码随想录 110. 平衡二叉树讲解

视频讲解:后序遍历求高度,高度判断是否平衡 | LeetCode:110.平衡二叉树

思路和解法

题目:
给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
想法:
肯定是要遍历,那就用递归法,==这里总结一下心得,用递归法深度遍历就要考虑哪种遍历顺序,根据就是要做什么处理,比如这道题,要判断子树的信息,那就是后序遍历。==定义递归函数的意义:返回以传入节点为根节点的树的高度。一个细节就是判断是否为高度平衡二叉树,用-1表示不是,如果子节点不是高度平衡二叉树,那当前的节点也肯定不是了,算是一个小优化。然后就是本节点的处理:要算上当前节点,也就是高度+1再返回。

/**
 * 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:
    //递归函数 返回以传入节点为根节点的树的高度
    int getHeight(TreeNode* node) {
        //终止条件 走到了空节点 返回高度0
        if (node == nullptr) {
            return 0;
        }
        //如果不是空节点,获取以子节点为根节点的树的高度,判断是否满足平衡二叉树,如果不满足,没有必要再计算
        int leftHeight = getHeight(node -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node -> right);
        if (rightHeight == -1) return -1;
        //用-1代表不满足平衡二叉树
        if (abs(leftHeight - rightHeight) > 1) return -1;
        //如果满足平衡二叉树,返回以传入节点为根节点的树的高度
        return max(leftHeight, rightHeight) + 1;
    }

    bool isBalanced(TreeNode* root) {
        int result = getHeight(root);
        if (result == -1) return false;
        return true;
    }
};

题目链接:leetcode 257. 二叉树的所有路径

文章讲解:代码随想录 257. 二叉树的所有路径讲解

视频讲解:递归中带着回溯,你感受到了没?| LeetCode:257. 二叉树的所有路径

思路和解法

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

叶子节点 是指没有子节点的节点。
想法:
这里提及了回溯算法。我的理解就是有递归就要有回溯,但是是有前提的,前提就是只有当递归以后改变了传入参数的信息,并且传入参数在本次递归中还需要利用的就需要回溯,也就是把修改的内容去除掉。对于传值而非传递引用的递归函数就不需要回溯了。回溯只需要考虑递归一层以后的结果,不需要继续向下考虑,因为回溯操作在递归函数里,下一层的递归所需要的回溯在下一层递归函数里解决。

还有就是讲解中对于版本二的代码的讲解我认为有点问题,讲解中认为"->“是需要回溯的,但我认为不是真正意义的回溯,只是在本层处理中向下递归的入参不能错,而向我下面代码写的那样,”->"的添加放在if语句的外面就可以了,本质上pop操作的原因并不是递归引起的。

/**
 * 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:
    void traversal(TreeNode* node, vector<int>& path, vector<string>& result) {
        //处理当前节点
        path.push_back(node -> val);        
        //终止条件
        if (!node -> left && !node -> right) {
            //把path转化为一个结果放入result
            string s;
            //因为要加"->",最后一个要单独处理
            for (int i = 0; i < path.size() - 1; i++) {
                s += to_string(path[i]);
                s += "->";
            }
            s += to_string(path[path.size() - 1]);
            result.push_back(s);
            return ;
        }
        //递归+回溯
        if (node -> left) {
            traversal(node -> left, path, result);
            //此时path,result都被改变了,为了递归右节点,需要pop掉,
            //path加内容只考虑一层,因为这个函数是递归函数,在下一次调用的时候也会考虑到下下层的递归
            path.pop_back();
        }
        //因为对于上一层的递归,path在这里也被改了,所以为了上一层能返回正常结果,这里也要pop掉
        if (node -> right) {
            traversal(node -> right, path, result);
            path.pop_back();
        }
        return ;
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        traversal(root, path, result);
        return result;
    }
};
//版本二
// class Solution {
// private:
//     void traversal(TreeNode* cur, string path, vector<string>& result) {
//         path += to_string(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中
//         if (cur->left == NULL && cur->right == NULL) {
//             result.push_back(path);
//             return;
//         }
//         path += "->";
//         if (cur->left) {
//             traversal(cur->left, path, result); // 左
//             // path.pop_back(); // 回溯 '>'
//             // path.pop_back(); // 回溯 '-'
//         }
//         if (cur->right) {
//             // path += "->";
//             traversal(cur->right, path, result); // 右
//             // path.pop_back(); // 回溯'>'
//             // path.pop_back(); // 回溯 '-'
//         }
//     }

// public:
//     vector<string> binaryTreePaths(TreeNode* root) {
//         vector<string> result;
//         string path;
//         if (root == NULL) return result;
//         traversal(root, path, result);
//         return result;

//     }
// };

题目链接:leetcode 404.左叶子之和

文章讲解:代码随想录 404.左叶子之和讲解

视频讲解:二叉树的题目中,总有一些规则让你找不到北 | LeetCode:404.左叶子之和

思路和解法

题目:
给定二叉树的根节点 root ,返回所有左叶子之和。
想法:
这道题目对于左叶子的判断是核心。其余遵循递归法的流程即可,注释中全部写出来了。

/**
 * 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:
    //思路:递归法
    //明确左叶子的定义,即判断条件 当前节点有左子节点,且该左子节点不含左右子节点
    int sumOfLeftLeaves(TreeNode* root) {
        //定义返回值类型为int为当前节点的所有左叶子之和 入参为当前节点,所以用题目给的函数作为递归函数即可
        //终止条件
        if (root == nullptr) {
            return 0;
        }
        //当前节点的处理逻辑 如何计算当前节点的左叶子之和 
        //递归计算当前节点的左子节点的左叶子之和,然后是右子节点的左叶子之和,加在一起
        int leftSum = sumOfLeftLeaves(root -> left);
        int rightSum = sumOfLeftLeaves(root -> right);
        //还有一部分就是判断左子节点本身是不是一个左叶子,如果是把该节点的值也加上
        if (root -> left && !root -> left -> left && !root -> left -> right) {
            return leftSum + rightSum + root -> left -> val;
        }
        return leftSum + rightSum;
    }
};
文章来源:https://blog.csdn.net/Tong_1024_/article/details/135564423
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。