深度優(yōu)先遍歷（DFS，全稱為DepthFirstTraversal），是我們樹或者圖這樣的數(shù)據(jù)結(jié)構(gòu)中常用的?種遍歷算法。這個算法會盡可能深的搜索樹或者圖的分?，直到?條路徑上的所有節(jié)點都被遍歷完畢，然后再回溯到上?層，繼續(xù)找?條路遍歷。
在?叉樹中，常?的深度優(yōu)先遍歷為：前序遍歷、中序遍歷以及后序遍歷。
?三種遍歷方式的最大區(qū)別是：處理根節(jié)點的時機不同。?

1、計算布爾二叉樹的值

//后序遍歷
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left == nullptr) return root->val;
        bool l = evaluateTree(root->left);
        bool r = evaluateTree(root->right);
        if(root->val == 2) return l | r;
        else return l & r;
    }
};

2、求根節(jié)點到葉節(jié)點數(shù)字之和?

class Solution {
public:
    int dfs(TreeNode* root,int presum)
    {
        presum = presum*10+root->val;

        if(root->left == nullptr && root->right == nullptr) return presum;
        int ret = 0;

        if(root->left) ret += dfs(root->left,presum);
        if(root->right) ret += dfs(root->right,presum);
        return ret;
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
};

3、二叉樹剪枝

?????????

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

4、驗證二叉搜索樹

/**
 * 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:
    long prev = LONG_MIN;

    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 && right && cur;
    }
};

?5、二叉搜索樹中第K小的元素

/**
 * 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 count;
    int ret;
    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);
    }
};

6、二叉樹的所有路徑

文章來源地址http://www.zghlxwxcb.cn/news/detail-726793.html

/**
 * 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:
    vector<string> ret;

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

到了這里，關(guān)于專題二：二叉樹的深搜【遞歸、搜索、回溯】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！