分类 深度优先搜索 下的文章

验证二叉搜索树

问题描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree

思路

将树按中序遍历的顺序存储在vector array中。
令vector tmp=array,将tmp排序，并去重。
去重的目的是判断数的元素是否都严格大于或者小于，因为搜索二叉树中不存在等于的元素。
如果树是搜索二叉树，那么中序遍历得到的数组一定是从大到小排序的。

题解

class Solution {
public:
    vector<int> array;

    bool isValidBST(TreeNode *root) {
        dfs(root);
        vector<int> tmp;
        tmp=array;
        sort(tmp.begin(),tmp.end());
        tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
        return tmp == array;
    }

    void dfs(TreeNode *node) {
        if (node == nullptr)return;
        dfs(node->left);
        array.push_back(node->val);
        dfs(node->right);
    }
};

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

问题描述

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

思路

二叉搜索树的性质是，根节点的左边比其小，右边比其大。
本题的思路是将搜索二叉树存到一个vector ret中，ret升序排列的。
题目要求第k小的元素，所以ret[k-1]即为最终结果。

题解

class Solution {
public:
    vector<int> ret;
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return ret[k-1];
    }
    void dfs(TreeNode *node){
        if(node== nullptr) return;
        dfs(node->left);
        ret.push_back(node->val);
        dfs(node->right);
    }
};

全排列

问题描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations

思路

回溯算法，和以前的做法一样，详情见以前的题目。

题解

class Solution {
public:
    bool visited[100] = {false};
    vector<int> B;
    vector<vector<int> > A;

    vector<vector<int>> permute(vector<int> &nums) {
        dfs(nums,A,0);
        return A;
    }
    void dfs(vector<int> &nums, vector<vector<int>> &A, int step) {
        int n = nums.size();
        if (step == n) {
            A.push_back(B);
            return;
        }
        for (int i = 0; i <n;i++)
        {
            if(visited[i]==false)
            {
                visited[i]=true;
                B.push_back(nums[i]);
                dfs(nums,A,step+1);
                visited[i]= false;
                B.pop_back();
            }
        }
    }
};

电话号码的字母组合

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

17_telephone_keypad.png

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

思路

首先在电话号码的数字和字母之间进行一个映射， map<char, string> table;
vector ret作为最后返回的结果，cur作为中间暂存结果，当递归次数index等于digits.length()时，将cur存入到ret中
当index小于digits.length()时，

for(int i=0;i<table[digits[index]].length();i++){
            dfs(digits,cur + table[digits[index]][i],index + 1);
        }

题解

class Solution {
public:
    map<char, string> table;

    void init() {
        table['2'] = "abc";
        table['3'] = "def";
        table['4'] = "ghi";
        table['5'] = "jkl";
        table['6'] = "mno";
        table['7'] = "pqrs";
        table['8'] = "tuv";
        table['9'] = "wxyz";
    }

    int len;
    vector<string> ret;

    vector<string> letterCombinations(const string &digits) {
        init();
        len = digits.length();
        if(len==0) return ret;
        dfs(digits, "",0);
        return ret;
    }

    void dfs(string digits, const string &cur,int index) {
        if (index == len) {
            ret.push_back(cur);
            return;
        }
        for(int i=0;i<table[digits[index]].length();i++){
            dfs(digits,cur + table[digits[index]][i],index + 1);
        }

    }
};

括号生成

问题描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

本题用了回溯算法来生成括号组合。

在最开始需要注意的地方是，n是括号的对数，所以递归的步数应该是n=n*2。
每次递归的选择只有‘（’和“）”两种选择。
当递归的次数到达n时在返回上一层递归时，要先判断是不是有效的括号组合，如果是有效的括号组合，则将括号组合插入到返回结果vector<int> A中。
返回上一层递归后，删除字符串的最一个字符用 str.substr(0, str.length() - 1)

判断字符是否为有效括号组合：

如果字符为“（”，那么将其push到栈中，如果为“）”那么在栈中弹出一个“）”。
当栈为空的时候弹出“）”则直接可以判断不是一个有效的括号组合。
到最后的时候栈不为空，则说明“（”比较多，也说明不是有效的括号组合。

题解


class Solution {
public:
    vector<string> A;

    vector<string> generateParenthesis(int n) {
        n = n * 2;
        dfs(n, 0, A);
        return A;
    }

    string str;

    void dfs(int n, int step, vector<string> &A) {

        if (step == n) {
            if (alter(str) == 0) {
                A.push_back(str);
            }
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                str = str + "(";
            } else {
                str += ")";
            }
            dfs(n, step + 1, A);
            str = str.substr(0, str.length() - 1);
        }
    }

    int alter(string string1) {
        stack<string> stack1;
        int n = string1.length();
        for (int i = 0; i < n; i++) {
            if (string1[i] == '(') {
                stack1.push("(");
            } else if (string1[i] == ')') {
                if (!stack1.empty()) { stack1.pop(); }
                else {return -1;}
            }
        }
        if (stack1.empty()) {
            return 0;
        } else {
            return -1;
        }
    }
};
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5