【DFS】汉诺塔问题 / 反转链表 / 求根节点到叶节点数字之和 / 验证二叉搜索树

_小羊_

发布于 2025-04-09 00:40:52

11300

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

面试题 08.06. 汉诺塔问题

面试题 08.06. 汉诺塔问题

要将a柱上n个的盘子借助b柱放到c柱上，应该先将a柱上的n-1个盘子借助c放到b上，然后再将b柱上的n-1个盘子借助a柱放到c柱上，以此往复。

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
        if (n == 1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1); // a柱上的n-1个盘子借助c柱放到b柱上
        c.push_back(a.back());
        a.pop_back();
        dfs(b, a, c, n - 1);
    }
};

合并两个有序链表

合并两个有序链表

重复子问题：合并两个有序列表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } 
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } 
    }
};

反转链表

反转链表

单链表可以看作一棵树。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

两两交换链表中的节点

两两交换链表中的节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = newhead;
        return ret;
    }
};

Pow(x, n)

Pow(x, n)

当n过大时，我们可以先算x的n/2次方，依此递归，然后相乘。

另外对负数取正可能会超出int范围，所以要强转成long类型。

class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -(long)n) : pow(x, n);
    }

    double pow(double x, long n)
    {
        if (n == 0) return 1;
        double num = pow(x, n / 2);
        return n % 2 == 0 ? num * num : num * num * x;
    }
};

计算布尔二叉树的值

计算布尔二叉树的值

很明显是对二叉树的后序遍历。

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

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

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

dfs前序遍历：前序遍历按照根节点、左子树、右子树的顺序遍历二叉树的所有节点，通常用于子节点的状态依赖于父节点状态的题。

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

二叉树剪枝

二叉树剪枝

dfs后序遍历：后序遍历按照左子树、右子树、根节点的顺序遍历二叉树的所有节点，通常用于父节点的状态依赖于子节点状态的题目。

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

验证二叉搜索树

验证二叉搜索树

二叉搜索树的中序遍历的结果一定是一个严格递增的序列。 可以初始化一个无穷小的全区变量用来记录中序遍历过程中的前驱结点，那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下一层的递归中。

在递归问题中有时可以使用全局变量，从而减少参数的传递；
根据条件增加剪枝操作，降低时间复杂度。

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

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

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

中序遍历二叉搜索树，找到第k个数即可。

在递归问题中使用全局变量可以减少参数的传递。

class Solution {
    int ret, count;
public:
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        dfs(root->left);
        if (--count == 0) ret = root->val;
        dfs(root->right);
    }
};

二叉树的所有路径

二叉树的所有路径

回溯问题中往往需要我们恢复现场，例如使用全局变量等。如果参数是局部变量，利用传值传参会在不同的栈帧中拷贝各自的数据，因此不会改变参数，也就不需要我们手动恢复现场了。

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