day 17 二叉树（四）

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;
    }
};