day 17 二叉树(四)

2023-12-15 15:40:22

day17
2023.12.15
代码随想录

1. 110平衡二叉树
首先本题一看就是偏递归的题,一个平衡二叉树的左右子树也一定是平衡二叉树;其次就是高度的问题,判断平衡二叉树是要根据左右节点的高度只差判断的;高度怎么求呢,做了这么多树的题目了,也明白,高度就是递归深度!而且是最大的那个,所以求高度的代码不就有了,每递归一层,高度加一,然后比较左右子树的高度,返回最大的那个!最后在判别平衡二叉树中,高度差的绝对值如果大于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:
    bool isBalanced(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }

    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);

    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }

    return isBalanced(root->left) && isBalanced(root->right);
}

int getHeight(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }

    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);

    return 1 + max(leftHeight, rightHeight);
    }
};

这就是完整逻辑,但最后我对递归产生了质疑,感觉,递归怎么有点不太有用了,好像最后返回true也行?就试了试,但没通过,看了官方给出的未通过的测试用例:
在这里插入图片描述
这种情况下,虽然根节点满足高度差小于1,但左右子树明显不是。所以还是得递归!悟了!

2. 257二叉树得所有路径
这道题感觉有难度啊,为什么leetcode定义为简单。。。
首先访问路径,一定是要深度遍历得,也就离不开递归了。
定义一个存储路径值得变量(path),和一个结果变量(result)。递归中给path存储值,直到叶子节点,也就是左右节点都为NULL,此时将path所有值按要求打印为string,然后存入result。
开始这么写,就有问题了,这样写的结果是把所有路径累加在一起了,我们新的访问函数需要将之前path里的值删去,也就是访问结束一个节点,需要将该节点val从path中弹出,也就是回溯!,至于何时弹出,其实不用多想,我们执行时一定是叶子节点,所以执行完函数后弹出即可!

/**
 * 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:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(root==NULL) return result;
        travel(root, path, result);
        return result;
    }
    void travel(TreeNode*node, vector<int>& path, vector<string>& result){
        path.push_back(node->val);
        if(node->left==NULL && node->right==NULL){
            string st;
            for(int i=0;i<path.size()-1;i++){
                st +=to_string(path[i]);
                st +="->";
            }
            st +=to_string(path[path.size()-1]);
            result.push_back(st);
            return;
        }
        if(node->left){
            travel(node->left, path, result);
            path.pop_back();

        }
        if(node->right){
            travel(node->right, path, result);
            path.pop_back();
        }
    }
};

3. 404左叶子之和
这道题也挺有意思,一看就是递归,不过开始题看错了,以为是左节点之和。。。写了后提交,某些测试用例不通过,才反映过来,不过也好说,进一步修改就行了,给递归函数加了bool参数,是左节点为true,这样递归最后看是叶子节点,且该参数为true,在加入sum即可!

/**
 * 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 sum=0;
        if(root==NULL) return 0;
        travel(root, sum, false);
        return sum;
    }
    void travel(TreeNode*node, int& sum, bool lef){
        if(node->left==NULL && node->right==NULL && lef)
            sum +=node->val;
        else if(node->left==NULL && node->right==NULL)
            return;

        if(node->left){
            travel(node->left, sum, true);
        }
        if(node->right)
            travel(node->right, sum, false);
        return;
    }
};

文章来源:https://blog.csdn.net/qq_56913257/article/details/135015223
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。