算法专题[递归-搜索-回溯-2-DFS]

一.计算布尔二叉树的值：

计算布尔二叉树的值

1.思路一：

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

        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);

        return root->val = (root->val==2? (left||right):(left&&right));
    }
};

2.GIF题目解析

二.求根节点到叶子节点的数字之和

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

1.思路一：

class Solution {
   
public:
    int dfs(TreeNode* root , int sum)
    {
   
        if(root==nullptr)
            return 0;
        sum = (sum*10)+(root->val);
        if(root->left==nullptr && root->right==nullptr)
        {
   
            return sum;
        }
        int ret = 0 ;
        if(root->left != nullptr) ret += dfs(root->left , sum );
        if(root->right != nullptr) ret += dfs(root->right , sum );
        return ret;
    }
    int sumNumbers(TreeNode* root) {
   
        return dfs(root , 0);;
    }
};

2.GIF题目解析

三.二叉树剪枝

二叉树剪枝

1.思路一：

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

2.GIF题目解析

四.验证二叉搜索树

验证二叉搜索树

1.思路一：

class Solution {
   
public:
    bool isValidBST(TreeNode* root) {
   
        if(root==nullptr)
            return true;
        
        bool left = isValidBST(root->left);
        if(root->val > prev)
            prev = root->val;
        else 
            return false;
        bool right = isValidBST(root->right);
        
        return left&&right;
    }
    long prev = LONG_MIN;
};

class Solution {
   
public:
    bool isValidBST(TreeNode* root) {
   
        if(root==nullptr)
            return true;
        
        bool left = isValidBST(root->left);
        if(left && root->val > prev)
            prev = root->val;
        else 
            return false;
        bool right = isValidBST(root->right);
        
        return left&&right;
    }
    long prev = LONG_MIN;
};

2.GIF题目解析

五.二叉搜索树中第k小的元素

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

1.思路一：

class Solution {
   
public:
    void dfs_1(vector<int>& dfs1 , TreeNode* root)
    {
   
        if(root==nullptr)
            return;
        
        int n = root->val;
        dfs1.push_back(n);
        dfs_1(dfs1 , root->left);
        dfs_1(dfs1 , root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
   
        //1.遍历：
        vector<int> dfs;
        dfs_1(dfs ,root);
        //2.排序：
        sort(dfs.begin(),dfs.end());
        return dfs[k-1];
    }
};

2.GIF题目解析

六.二叉树的所有路径

二叉搜索树的所有路径

1.思路一：

1.模拟路径去走判断到叶子节点然后给一个参数去push_back()
2.思路的函数参数是比较好的通过这样的参数可以解决很多问题。
3.特殊情况判断：只有一个节点的判断！

class Solution {
   
public:
    void dfs(TreeNode* root , string s , vector<string>& ret)
    {
   
        if(root == nullptr)
            return;

        int n = root->val;
        s += "->";
        s += to_string(n);

        //表示当前是叶子节点
        if(root->left == nullptr && root->right==nullptr)
        {
   
            ret.push_back(s);
            return;
        }
        dfs(root->left , s , ret);
        dfs(root->right , s , ret);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
   
        string s = to_string(root->val);
        vector<string> ret;
        if(root->left == nullptr && root->right==nullptr)
        {
   
            ret.push_back(s);
        }
        else
        {
   
            dfs(root->left , s , ret);
            dfs(root->right , s , ret);
        }
        return ret;
    }
};

2.GIF题目解析