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

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

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

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

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

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