输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。思路：二叉搜索树的中序遍历结果就是排序的。所以对二叉树进行中序遍历，遍历的过程中进行指针的调整，遍历完成就调整完毕。代码：/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; } }; */ class Solution { private: Node* pre; Node*
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。思路:三步走，先复制当前的复杂链表，如1->2->3,复制为1->1(copy)->2->2(copy)->3->3(copy)。然后，调整复制链表里的random指针，如果节点1的random指针存在，比如1->random = 3，则1(copy)->random = 1->random->next。最后一步拆分为两个链表。代码：/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。思路：深度优先遍历，每次遍历到叶子节点时，判断当前路径和是否等于目标和。如果等于则找到一个答案。代码：/** * 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 Solut
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。思路：因为是后续遍历，所以数组最后一个数就是根节点。从前往后扫描数组，如果某个数大于根节点的值，则停下，记这个数的下标为index,则index之前的数是左子树，然后继续扫描，如果出现小于根节点的数，则说明不是二叉搜索树的后序遍历结果，返回false，如果都大于根节点，则从index开始到根节点前一个数是右子树。对于左子树和右子树使用上述操作。代码：class Solution { public: bool verifyPostorderRes(vector<int>& postorder,int left, int right) { int index = left; for(;index < right;index++) { if(postorder[index] > postorder[right]) { b
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。思路：题意要求其实就是对二叉树进行广度优先遍历，打印出结果。代码：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> levelOrder(TreeNode* root) { if(root == nullptr) return {}; vector<int> ans; queue<TreeNode*> que; que.push(root); while(!que.empty()) {
