代码随想录刷题day13 | LeetCode 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和

110.平衡二叉树

力扣题目链接

后序遍历求高度，高度判断是否平衡 | LeetCode：110.平衡二叉树

1.三元运算符：（ ？ ：）

condition ? expression_if_true : expression_if_false;

前面是条件，如果符合就等于冒号前的expression_if_true，反之则是后面的。

2.如果要使用 if ( ! node -> left )，要注意空指针，下文如果要使用，可以先  if  ( node -> left )，也

就是我们所说的空指针不进入操作。 

3.abs（）绝对值函数

例如 if ( abs ( leftHeight - rightHeight ) > 1)  // 如果左右子树高度差大于 1，则不平衡 return -1;

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==nullptr)
            return true;
        return iB(root)==-1 ? false : true;
    }
    int iB(TreeNode* node)
    {
        if(node==nullptr)
            return 0;
        int leftnum=iB(node->left);
        if(leftnum==-1)
            return -1;
        int rightnum=iB(node->right);
        if(rightnum==-1)
            return -1;
        if(abs(leftnum-rightnum)>1)
            return -1;
        return max(leftnum,rightnum)+1;
    }
};

257. 二叉树的所有路径

 力扣题目链接

​​​​​​递归中带着回溯，你感受到了没？| LeetCode：257. 二叉树的所有路径

1.push_back（） 只能用来向 string 中添加单个字符

例如 str . push_back ( 'W' ) ;

而在vector<string>中，你可以使用push_back 来添加新的字符串

例如 result . push_back ( Spath ) ;

2.string 中 + = 可以添加字符串。

3.注意里面有回溯的过程

 path . pop_back ( ) ;

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        if(!root)
            return result;
        gettreePath(root,path,result);
        return result;
    }
    void gettreePath(TreeNode* node,vector<int> &path,vector<string> &result){
        path.push_back(node->val);
        if(!node->left&&!node->right){
            string Spath;
            for(int i=0;i<path.size()-1;i++){
                Spath+=to_string (path[i]);
                Spath+="->";
            }
            Spath+=to_string (path[path.size()-1]);
            result.push_back(Spath);
        }
        if(node->left){
            gettreePath(node->left,path,result);
            path.pop_back();
        }
        if(node->right){
            gettreePath(node->right,path,result);
            path.pop_back();
        }
    }
};

404.左叶子之和

力扣题目链接

二叉树的题目中，总有一些规则让你找不到北 | LeetCode：404.左叶子之和

关于getsum函数中 &sum，至于为什么这里要加引用呢？

如果不加引用，就是按值传递，每次进入递归函数时，sum 的值都会复制为当前的值，但修改的只

是副本。函数返回后，外部的 sum 仍然保持原始值，未发生任何累加，也就是0。

特别注意平时我们解二叉树的题目时，已经习惯了通过节点的左右孩子判断本节点的属性，而本题

我们要通过节点的父节点判断本节点的属性。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int result=0;
        if(!root)
            return 0;
        getsum(root,result);
        return result;
    }
    void getsum(TreeNode* node,int &sum){
        if(node->left&&!node->left->left&&!node->left->right)
            sum+=node->left->val;
        if(node->left)
            getsum(node->left,sum);
        if(node->right)
            getsum(node->right,sum);
    }
};