二叉树深搜专题篇

目录

计算布尔二叉树的值

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

二叉树剪枝

验证二叉搜索树

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

二叉树的所有路径

计算布尔二叉树的值

题目

思路

这道题其实是比较简单的，对二叉树来一次后序遍历即可，当遇到叶子结点直接返回叶子节点中的bool值即可，否则继续进行后序遍历，返回得到的左子树和右子树的计算结果。

代码

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left==nullptr) return root->val==0?false:true;
        bool left=evaluateTree(root->left);
        bool right=evaluateTree(root->right);
        return root->val==2?left|right:left&right;
    }
};

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

题目

思路

这道题所说的求根节点到叶节点数字之和，并非是求根节点到叶节点所有数字直接相加起来，而是将从根节点到叶节点路径上前一个位置的数字乘10+该位置的值，然后将所有从根节点到叶节点所有路径上的和相加起来。

直接来一次DFS即可，如果当前节点没有左孩子和右孩子，说明当前节点是叶节点，直接返回前一个位置的数字乘10+该位置的值即可，否则，DFS计算该节点左孩子那一侧得到的路径值以及该节点右孩子那一侧得到的路径值，然后返回二者之和即可。

代码

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }

    int dfs(TreeNode* root,int val){
        val=val*10+root->val;
        if(root->left==nullptr &&root->right==nullptr)
            return val;
        int ret=0;
        if(root->left) ret+=dfs(root->left,val);
        if(root->right) ret+=dfs(root->right,val);
        return ret;
    }
};

二叉树剪枝

题目

思路

题目中的描述“返回溢出所有不包含1的子树的原二叉树”，意思是剪掉不包含1的二叉树，如何判定某个位置是否应该被剪掉，来一次后序遍历即可，即先判断该位置左子树是否不包含1，以及该位置右子树是否不包含1，如果该位置左右子树都不包含1且该位置的值是0，那么就剪掉以该位置为根节点的子树，当遇到节点值是空时，直接返回空即可。

代码

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)
            root=nullptr;
        return root;
    }
};

验证二叉搜索树

题目

思路

我们可能会想到对二叉树来一次中序遍历，将中序遍历的结果存放到一个数组中，然后判断数组是否是升序的，因为对二叉搜索树进行中序遍历得到的结果是升序的，但是这样有些浪费空间，我们可以对二叉树进行中序遍历，使用一个变量prev记录中序遍历的前一个位置的值，每次到一个非空节点，判断该节点是否大于中序遍历前一个位置的值，如果大于，继续进行中序遍历，并更新prev的值为当前位置的值；否则直接返回false。其中prev事先初始化为LONG_MIN，因为这道题的节点值可能是INT_MIN。如果当前位置，当前位置的左子树，当前位置的右子树符合二叉搜索树的特点，返回true。

代码

class Solution {
    long prev=LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;
        bool left=isValidBST(root->left);
        //剪枝
        if(left==false) return false;

        bool cur=false;
        if(root->val > prev)
            cur=true;
        //剪枝
        if(cur==false) return false;

        prev=root->val;
        bool right=isValidBST(root->right);
        return left && cur && right;
    }
};

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

题目

思路

我们可能会想到遍历二叉搜索树，然后将所有节点的值添加到优先级队列中，然后就能够找到二叉搜索树中第K小的元素了，但是这样有些麻烦，不妨利用二叉搜索树的性质，对二叉树进行中序遍历，使用一个变量来记录当前位置是位于中序遍历的第几个位置，当正好是中序遍历的第K的位置，那么该位置的值就是二叉搜索树中第K小的元素。

代码

class Solution {
    int count,ret;
public:
    int kthSmallest(TreeNode* root, int k) {
        count=k;
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root){
        if(root==nullptr || count==0) return;
        dfs(root->left);
        count--;
        if(count==0) ret=root->val;
        dfs(root->right);
    }
};

二叉树的所有路径

题目

思路

这道题还是比较简单的，对二叉树进行一次DFS即可，当处理到叶节点的时候，直接返回得到的路径；否则，递归处理该位置左子树的路径以及该位置右子树的路径。

代码

class Solution {
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        dfs(root,path);
        return ret;
    }

    void dfs(TreeNode* root,string path){
        path+=to_string(root->val);
        if(root->left==nullptr && root->right==nullptr){
            ret.push_back(path);
            return;
        }
        path+="->";
        if(root->left) dfs(root->left,path);
        if(root->right) dfs(root->right,path);
    }
};