方法：递归对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分。具体做法：step 1：先根据前序遍历第一个点建立根节点。step 2：然后遍历中序遍历找到根节点在数组中的位置。step 3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。step 4：直到子树的序列长度为0，结束递归。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: TreeNode* reConstructBi...

方法一：DFS、路径比较1、利用深度优先搜索分别获取两个结点在二叉树中的路径；2、比较两个路径，得到最后相同的的结点即为两个结点的最近公共祖先。时间复杂度：o(n)。最坏情况需要遍历二叉树所有节点空间复杂度：o(n)。 class Solution { public: bool flag = false; //深度优先搜索（dfs） void dfs(TreeNode* root, vector<int>& path, int target) { if (root == nullptr || flag == true) ...

方法：BFS，辅助队列本质是广度优先搜索，利用辅助队列进行层序遍历。如果一个二叉树是完全二叉树，那么层序遍历时，第一个空结点也是它的最后一个空结点；否则就不是完全二叉树。时间复杂度：o(n)。最坏情况需要遍历二叉树的所有结点。空间复杂度：o(n)。需要辅助队列进行二叉树的层序遍历 class Solution { public: queue<TreeNode*> res; bool isCompleteTree(TreeNode* root) { if (root == nullptr) return true; ...

方法一：递归二叉搜索树的中序遍历一定是升序数组，所以可以利用递归遍历二叉树，如果前一个结点一定小于当前的结点，则可以判断二叉树为二叉搜索树；否则判断为非二叉搜索树。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: //初始化前结点值为最小值 long pre = INT_MIN; bool isValidBST(TreeNode* root) { if (root == nullptr) return true; //遍历左结点 if (!isValidBST(r...

方法：递归（中序遍历）对于二叉搜索树，中序遍历从小到大排序。通过递归实现二叉搜索树的中序遍历，并且改变结点的指针即可得到双向链表。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: TreeNode* head = nullptr; TreeNode* pre = nullptr; TreeNode* Convert(TreeNode* pRootOfTree) { //结点为空时，返回nullptr if (pRootOfTree == nullptr) return nul...

方法：辅助队列本质依然是广度优先搜索（BFS），与层序遍历本质相同，只是在偶数层时需要进行翻转。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > res; if (pRoot == nullptr) return res; queue<TreeNode*> q; ...

方法：辅助队列层序遍历本质就是广度优先搜索（BFS），通过构建辅助队列可以很好的得到二叉树的层序遍历。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: vector<vector<int> > levelOrder(TreeNode* root) { vector<vector<int> > res; if (root == nullptr) return res; queue<TreeNode*> q; ...

方法一：搜索路径比较得到两个目标值在二叉搜索数的路径，对两个路径进行比较，最后一个相同的结点就是最近的公共祖先时间复杂度：o(n)空间复杂度：o(n)。需要辅助队列存储路径 class Solution { public: //获取从根节点到目标值的路径 queue<TreeNode*> getPath(TreeNode* root, int target) { queue<TreeNode*> res; while (root->val != target) { res.push(roo...

方法：递归（自顶向下）经过每个结点都得到它的左子树和右子树的最大深度，判断每个结点的左右子树深度差是否大于1。深度差不大于1则继续递归。时间复杂度：o(n2)。第一个递归遍历二叉树所有节点，第二个递归查找深度最坏情况下（二叉树退化为链表）需要遍历二叉树所有节点。空间复杂度：o(n) class Solution { public: //获取树的最大深度 int getDepth(TreeNode* root) { if (root == nullptr) return 0; return max(getDepth(ro...

方法：递归二叉树的镜像就是将二叉树的每个结点都交换它的左右子结点。1、交换根结点的左右子结点；2、进入左子树和右子树不断地向下交换根结点的左右子结点。时间复杂度：o(n)空间复杂度：o(n)，递归栈的深度。 class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { //结点为空时，返回nullptr if (pRoot == nullptr) return nullptr; //交换根结点的左右子结点 TreeNode* temp = pRoot-&g...

方法：递归将问题分解为，合并当前结点和合并当前结点的两个二叉树两个部分。可以运用递归进行合并。时间复杂度：o(min(n,m))，m和n分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。空间复杂度：o(min(n,m))，递归栈深度也同时间，只访问了小树的节点数。 class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { //如果其中一个树的结点不存在，合并后的树节点即为另一个树的结点 if (t1 == nullptr) ...

方法一：递归一个对称的二叉树，两个不同方向的前序遍历一定是相同的。通过递归进行两个方向的遍历，终止条件为：当两个节点只有一个为空，或者两个节点的值不相同，则二叉树不对称。时间复杂度：o(n)空间复杂度：o(n)。递归栈的深度 class Solution { public: bool isSymmetrical(TreeNode* root1, TreeNode* root2) { //节点都为空时，返回true if (root1 == nullptr && root2 == nullptr) return ...

stackstack翻译为栈，是STL中实现的一个后进先出的容器。stack没有迭代器，因此无法通过下标快速访问元素（C ++迭代器用于对数据结构中的元素进行顺序访问或随机访问）。（1）push()push(x)将x入栈（2）top()top()获得栈顶元素（3）pop()pop()用以弹出栈顶元素（4）empty()empty()可以检测stack是否为空；返回true为空，返回false为非空（5）size()size()返回stack内元素的个数注意：在使用pop()和top()函数之前必须先使用empty()函数判断栈是否为空。vectorvector翻译为向量，vector是为了实现...

方法：递归既然是检查从根到叶子有没有一条等于目标值的路径，那肯定需要从根节点遍历到叶子，我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0. 而遍历的方法我们可以选取二叉树常用的递归前序遍历，因为每次进入一个子节点，更新sum值以后，相当于对子树查找有没有等于新目标值的路径，因此这就是子问题，递归的三段式为：终止条件： 每当遇到节点为空，意味着过了叶子节点，返回。每当检查到某个节点没有子节点，它就是叶子节点，此时sum减去叶子节点值刚好为0，说明找到了路径。返回值： 将子问题中是否有符合新目标值的路径层层往上返回。本级任务： 每一级需要检查是否到了叶子节点，如果没有...