2331. 计算布尔二叉树的值

二叉树遍历可以用递归来解决,该问题的简单子问题是 知道左右孩子的值，再根据| &返回true/false。左子树右子树的值交给dfs解决。

终止条件就是到达叶子节点，即没有左右孩子，因为是完全二叉树 所以只需要判断一个孩子是否存在就可以。

/**
 * 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 evaluateTree(TreeNode* root) {
        if(root->left==nullptr)//因为完全二叉树判断一个就可以
            return root->val;
        bool left=evaluateTree(root->left);
        bool right=evaluateTree(root->right);
        if(root->val==2) return (left||right);
        else return (left&&right);
    }
};

129. 求根节点到叶节点数字之和

数字总和=每一条路径累加的数字

怎么算路径上累加的数字呢？
拿图中的5举例，遍历完左孩子8就应该返回1258，5和8是知道的，但12呢？这就需要我们传递参数。所以函数头不仅需要当前节点的指针，还要有累加的数字12.

每遍历一个节点就累加当前节点的val，如果为叶子节点就直接返回，有孩子继续递归累加数字。

所以简单的子问题就是从根节点开始累加val，并传给左右叶子节点，累加数字并返回。

左右孩子还有孩子就交给dfs完成，直到叶子节点返回。

/**
 * 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 sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
    int dfs(TreeNode*root,int presum)
    {
        presum=presum*10+root->val;
        if(root->left==nullptr&&root->right==nullptr)
            return presum;
        int sum=0;
        if(root->left) sum+=dfs(root->left,presum);
        if(root->right) sum+=dfs(root->right,presum);
        return sum;
    }
};

814. 二叉树剪枝

什么时候可以处理root为当前节点的子树呢？当然是后序遍历完它的左右子树，获取左右子树的情况才能进行处理。

什么情况下可以删除它呢？左右子树+当前节点val==0时吗？可以，但不是最简单的情况。

我们后序遍历最先删除的肯定是为0的叶子结点，只要判断当前节点没有左右孩子+当前节点val==0就可以删除以当前节点为根的子树。

像上述左右子树+当前节点val==0，3个节点val都为0，根据上面的判断从叶子节点开始删也可以一个一个删除。

/**
 * 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:
    TreeNode* pruneTree(TreeNode* root) {
        if(root==nullptr)return nullptr;
        root->left=pruneTree(root->left);
        root->right=pruneTree(root->right);
        if(root->left==nullptr&&root->right==nullptr&&root->val==0)
        {
            //delete root;
            root=nullptr;
        }
        return root;
    }
};

98. 验证二叉搜索树

我们知道搜索二叉树的中序遍历是有序的。我们定义一个全局的变量prve记录上一个遍历数的大小，进行中序遍历，如果prve不是单调变化的，就说明它不是二叉搜索树。

判断左子树 判断当前节点 判断右子树

剪枝：

1.判断完左子树如果返回的false，就可以直接返回false

2.判断当前节点也是，是fasle就直接返回，不是就更新prve

/**
 * 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 {
    long prve=LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;
        bool left=true,right=true;
        if(root->left) left=isValidBST(root->left);
        //剪枝
        if(left==false) return false;
        if(prve<root->val) prve=root->val;
        else return false;
        if(root->right) right=isValidBST(root->right);
        return left&&right;
    }
};

细节：因为节点最小值为INT_MIN，所以prve类型为logn 定义为LONG_MIN

230. 二叉搜索树中第 K 小的元素

和上道题一样，通过中序排序就可以找第k小的数。

建议定义两个全局变量，kq判断是否到第K个数，re记录要返回的值。

/**
 * 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 {
    int re=-1;
    int kq;
public:
    int kthSmallest(TreeNode* root, int k) {
        kq=k;
        dfs(root);
        return re;
    }
    void dfs(TreeNode* root)
    {
        if(root==nullptr||kq==0) return;
        dfs(root->left);
        if(--kq==0)
        {
            re=root->val;
            return;
        }
        dfs(root->right);
        return;
    }
};

257. 二叉树的所有路径

 深度遍历二叉树时，用一个path字符串来记录经过的结点：不是叶子节点加val->，叶子节点加val，并返回。返回到哪里？可以定义一个全局的string数组，记录每条路径。

path字符串可以定义成全局的吗？

我们知道当访问到4叶子节点时，就要回溯到2，此时path:1->2->4变成1->2

如果定义成全局变量每次回溯都要进行手动恢复path。

因此我们可以把path当作参数传给递归函数，每个函数栈中都会保存一份path，当递归返回到上一层时，上一层的 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 {
    vector<string> re;
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path="";
        dfs(root,path);
        return re;
    }
    void dfs(TreeNode*root,string path)
    {
        if(root==nullptr) return;
        if(root->left||root->right)
            path+=to_string(root->val)+"->";
        else
        {
            path+=to_string(root->val);
            re.push_back(path);
        }
        dfs(root->left,path);
        dfs(root->right,path);
            
    }
};