代码随想录day17

110.平衡二叉树

????????给定一个二叉树，判断它是否是高度平衡的二叉树。

????????本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

????????给定二叉树 [3,9,20,null,null,15,7]返回true

? ? ? ? 前置知识：

? ? ? ? （1）求深度可以从上到下去查 所以需要前序遍历（中左右）

? ? ? ? （2）求高度只能从下到上去查，所以只能后序遍历（左右中）

????????根基平衡二叉树的定义：左右子树之差不超过1，因此需要求每个节点的左右子树的高度之差，求高度应使用后序遍历，而判断时用先序顺序，先判断当前节点是否满足条件，再判断左右子树是否也满足条件。

int getheigh(struct TreeNode* t){
    if(t==NULL) return 0;
    int left=getheigh(t->left);
    int right=getheigh(t->right);
    return fmax(left,right)+1;
}
bool isBalanced(struct TreeNode* root) {
    if(root==NULL) return true;
    int left=getheigh(root->left);
    int right=getheigh(root->right);
    if(abs(left-right)<=1){
        //当前节点满足条件，递归遍历左右子树
        return isBalanced(root->left)&&isBalanced(root->right); 
    }
    return false;
}

257. 二叉树的所有路径?

?????????给定一个二叉树，返回所有从根节点到叶子节点的路径。

????????说明: 叶子节点是指没有子节点的节点。

? ? ? ? 详细版本

????????此题涉及到回溯算法，每次处理完一条分支之后，要层层向上返回，即弹出path中的元素。

class Solution {
public:
    void travelsal(TreeNode* cur,vector<int> &path,vector<string> &ans){
        path.push_back(cur->val);//保证最后一个节点也能加入path中
        if(cur->left==nullptr&&cur->right==nullptr){
            //叶子节点，将要当前路径按格式压入答案中
            string spath;
            for(int i=0;i<path.size()-1;++i){
                spath+=to_string(path[i]);
                spath+="->";
            }
            //最后一个字母单独处理
            spath+=to_string(path[path.size()-1]);
            ans.push_back(spath);
            return;
        }
        if(cur->left){
            travelsal(cur->left,path,ans);
            path.pop_back();//回溯
        }
        if(cur->right){
            travelsal(cur->right,path,ans);
            path.pop_back();//回溯
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        vector<int> path;
        if (root == NULL) return ans;
        travelsal(root,path,ans);
        return ans;
    }
};

? ? ? ? ?精简版本:隐藏了回溯的过程

????????定义的是string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果。每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。

class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

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

    }
};

?404.左叶子之和

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

? ? ? ? 左叶子节点是指左侧的叶子结点。

????????判断左叶子，不是二叉树左侧节点,判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

? ? ? ? 先序遍历

????????需要判断当前节点的做孩子是否存在，如果存在还需要判断是否是叶子节点，若是，则进行累加。

class Solution {
public:
    void count(TreeNode* root,int &sum){
        if(root==nullptr){
            return;
        }
        if(root->left!=nullptr){//若存在左孩子
            TreeNode *temp=root->left;
            if(temp->left==nullptr&&temp->right==nullptr)//若该节点为叶子结点
                sum+=root->left->val;
        }
        count(root->left,sum);
        count(root->right,sum);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int sum=0;
        count(root,sum);
        return sum;
    }
};

? ? ? ? 后序遍历

????????从下向上一层一层返回左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr) return 0;
        if(root->left==nullptr&&root->right==nullptr) return 0;
        int sum=0;
        int leftValue=sumOfLeftLeaves(root->left);    // 左
        if (root->left&&!root->left->left&&!root->left->right) { // 左子树就是一个左叶子的情况
            leftValue=root->left->val;
        }
        int rightValue=sumOfLeftLeaves(root->right);  // 右

        int sum=leftValue+rightValue;               // 中
        return sum;
    }
};