二叉树中和为某一值的路径

发表于 2020-02-07 更新于 2020-02-12

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

深搜，找到则保存。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void DoFindPath(TreeNode* root,int expectNumber)
    {
        if (root == nullptr)
        {
            if (expectNumber == 0 && path.size() > 0)
            {
                result.push_back(path);
            }
        }
        else
        {
            path.push_back(root->val);
            if (root->left == nullptr)
            {
                if (root->right == nullptr)
                {
                    if (root->val == expectNumber)
                    {
                        result.push_back(path);
                    }
                }
                else
                {
                    FindPath(root->right, expectNumber - root->val);
                }
            }
            else
            {
                FindPath(root->left, expectNumber - root->val);
                if (root->right != nullptr)
                {
                    FindPath(root->right, expectNumber - root->val);
                }
            }
            path.pop_back();
        }
    }
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber)
    {
        DoFindPath(root, expectNumber);
        return result;
    }
};

二叉搜索树的后序遍历序列

发表于 2020-02-07 更新于 2020-02-12

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

若是，则对其任意子树的序列，其末尾元素大于序列中的前若干个元素，而小于其他元素。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0)
        {
            return false;
        }
        else if (sequence.size() == 1)
        {
            return true;
        }
        else
        {
            const int root = sequence[sequence.size() - 1];
            bool is_left_part = true;
            int first_right_index = -1;
            for (int i = 0; i < sequence.size(); i++)
            {
                if (is_left_part)
                {
                    if (sequence[i] > root)
                    {
                        first_right_index = i;
                        is_left_part = false;
                    }
                }
                else
                {
                    if (sequence[i] < root)
                    {
                        return false;
                    }
                }
            }
            if (first_right_index <= 0)
            {
                return VerifySquenceOfBST(vector<int>(sequence.begin(), sequence.begin() + sequence.size() - 1));
            }
            else
            {
                return VerifySquenceOfBST(vector<int>(sequence.begin(), sequence.begin() + first_right_index)) \
                    && VerifySquenceOfBST(vector<int>(sequence.begin() + first_right_index, sequence.end()));
            }
        }
    }
};

从上往下打印二叉树

发表于 2020-02-07 更新于 2020-02-12

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

从上到下一层一层即广度优先，即队列。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
    public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> nodes;
        nodes.push(root);
        while(nodes.size())
        {
            TreeNode *next = nodes.front();
            nodes.pop();
            if (next != nullptr)
            {
                result.push_back(next->val);
                nodes.push(next->left);
                nodes.push(next->right);
            }
        }
        return result;
    }
};

栈的压入、弹出序列

发表于 2020-02-07 更新于 2020-02-12

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

对顺序压入、弹出后序列，其入栈前、出栈后的序列刚好相反，故反向遍历两序列，并引入临时栈以处理不连续压入、弹出时栈中遗留的元素。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> temp;
        auto push_i = pushV.rbegin();
        auto pop_i = popV.begin();
        while (pop_i != popV.end())
        {
            if (temp.size() != 0 && temp.top() == *push_i)
            {
                temp.pop();
                push_i++;
            }
            else if (*push_i == *pop_i)
            {
                push_i++;
                pop_i++;
            }
            else
            {
                temp.push(*pop_i);
                pop_i++;
            }
        }
        if (temp.size() == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

包含min函数的栈

发表于 2020-02-07 更新于 2020-02-12

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

class Solution {
public:
    stack<int> data, mins;
    void push(int value) {
        data.push(value);
        if (mins.size() > 0)
        {
            const int old_min = mins.top();
            if (old_min < value)
            {
                mins.push(old_min);
            }
            else
            {
                mins.push(value);
            }
        }
        else
        {
            mins.push(value);
        }
    }
    void pop() {
        data.pop();
        mins.pop();
    }
    int top() {
        return data.top();
    }
    int min() {
        return mins.top();
    }
};

顺时针打印矩阵

发表于 2020-02-07 更新于 2020-02-12

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

一圈一圈地自外向内打印，最后一圈对单行/单列的情况做特别处理。

class Solution {
public:
    void printCircle(vector<vector<int> > &matrix,
                     const int width, const int height,
                     const int start, vector<int> &disk)
    {
        if (width == 1)
        {
            for (int x = start; x < start + height; x++)
            {
                disk.push_back(matrix[x][start]);
            }
        }
        else if (height == 1)
        {
            for (int y = start; y < start + width; y++)
            {
                disk.push_back(matrix[start][y]);
            }
        }
        else
        {
            for (int y = start; y < start + width - 1; y++)
            {
                disk.push_back(matrix[start][y]);
            }
            for (int x = start; x < start + height - 1; x++)
            {
                disk.push_back(matrix[x][start + width - 1]);
            }
            for (int y = start + width - 1; y > start; y--)
            {
                disk.push_back(matrix[start + height - 1][y]);
            }
            for (int x = start + height - 1; x > start; x--)
            {
                disk.push_back(matrix[x][start]);
            }
        }
    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        const int width = matrix[0].size();
        const int height = matrix.size();
        vector<int> result;
        if (width == 0 || height == 0)
        {
            return result;
        }
        else
        {
            int start = 0;
            while (width > start * 2 && height > start * 2)
            {
                printCircle(matrix, width - start * 2,
                            height - start * 2, start, result);
                start++;
            }
            return result;
        }
    }
};

二叉树的镜像

发表于 2019-09-30 更新于 2020-02-12

操作给定的二叉树，将其变换为源二叉树的镜像。

遍历各节点，交换其子节点。
递归或任意一种遍历。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (pRoot != nullptr)
        {
            TreeNode *left = pRoot->left;
            pRoot->left = pRoot->right;
            pRoot->right = left;
            Mirror(pRoot->left);
            Mirror(pRoot->right);
        }
    }
};

树的子结构

发表于 2019-09-30 更新于 2020-02-12

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

从根开始完全相等(is)，或在左、右子树(has)。

对于相等(is)，同时遍历。
对于存在(has)，遍历树A。

综上：

遍历树A
1. 若A的当前节点与B的根一致
  2. 遍历树B

递归或队列（层次遍历）或栈（前序、中序、后续）均可。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool IsSubtree(const TreeNode const * pRoot1, const TreeNode const * pRoot2)
    {
        if (pRoot2 == nullptr)
        {
            return true;
        }
        else if (pRoot1 == nullptr)
        {
            return false;
        }
        else
        {
            return pRoot1->val == pRoot2->val && \
                IsSubtree(pRoot1->left, pRoot2->left) && \
                IsSubtree(pRoot1->right, pRoot2->right);
        }
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if (pRoot1 == nullptr || pRoot2 == nullptr)
        {
            return false;
        }
        else
        {
            return IsSubtree(pRoot1, pRoot2) || \
                HasSubtree(pRoot1->right, pRoot2) || \
                HasSubtree(pRoot1->left, pRoot2);
        }
    }
};

合并两个排序的链表

发表于 2019-09-30 更新于 2020-02-12

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode * const head = new ListNode(INT_MIN);
        ListNode *current = head;
        ListNode *a = pHead1, *b = pHead2;
        while (true)
        {
            if (a == nullptr)
            {
                if (b == nullptr)
                {
                    break;
                }
                else
                {
                    current->next = b;
                    break;
                }
            }
            else
            {
                if (b == nullptr)
                {
                    current->next = a;
                    break;
                }
                else
                {
                    if (a->val < b->val)
                    {
                        current->next = new ListNode(a->val);
                        current = current->next;
                        a = a->next;
                    }
                    else
                    {
                        current->next = new ListNode(b->val);
                        current = current->next;
                        b = b->next;
                    }
                }
            }
        }
        ListNode * const first = head->next;
        delete head;
        return first;
    }
};

反转链表

发表于 2019-09-30 更新于 2020-02-12

输入一个链表，反转链表后，输出新链表的表头。

先保存子节点。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr)
        {
            return pHead;
        }
        else
        {
            ListNode *last = pHead;
            ListNode *current = pHead->next;
            ListNode *next = current->next;
            last->next = nullptr;
            current->next = last;
            while (next != nullptr)
            {
                last = current;
                current = next;
                next = next->next;
                current->next = last;
            }
            return current;
        }
    }
};