牛客159707358号

分类

/ 注册

TA的专栏 40篇文章 0人订阅

剑指offer回顾

40篇文章 116人学习

全部文章（共99篇）

题解 | 判断是不是平衡二叉树 JZ79 来自专栏

递归法问题拆分，平衡=左子树平衡+右子树平衡+高度差为1不能简单递归，因为必须比较左右子树的高度，递归返回的结果包含高度和左右子树是否平衡结果用返回双值来避免两个递归函数调用 /** * struct TreeNode { * int val; * struct TreeNode *left;...

2025-03-23

0 60

题解 | 二叉搜索树与双向链表来自专栏

递归遍历中序遍历修改全局变量的指针，且不改变当前函数栈帧pRootOfTree的指针的right。注意head是变化，多一个变量保存head。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right...

2025-03-23

0 38

题解 | 二叉搜索树的后序遍历序列来自专栏

构建搜索二叉树+后序遍历构建搜索二叉树->后序遍历->比较顺序搜索二叉树的结构和后序遍历是一一对应的，通过逆后序遍历可以重新构建唯一的二叉树。 class Solution { public: void buildTree(TreeNode* cur,TreeNode* fron...

2025-03-23

0 88

题解 | 树的子结构 JZ26 定头节点+比较树结构来自专栏

递归法问题拆分成：已知头节点比较两颗树是否相同（递归函数一）+ 遍历树的节点作为比较起点（递归函数二）注意空指针判断 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(i...

2025-03-23

0 66

题解 | 重建二叉树 JZ27 复杂递归来自专栏

递归法把构建树可以转化成构建子树，递归法的基础并没有完全想象出整个过程，大致写法+边界处理left<rightC++使用索引+引用的方式，python可以直接选择数组 /** * struct TreeNode { * int val; * struct TreeNode *left; ...

2025-03-22

0 44

题解 | 二叉搜索树的第k个节点 JZ54 二叉搜索树的中序就是数据升序

递归法二叉搜索树的中序就是数据升序，升序序列可以求得第k个可以使用全局变量只保留第k个 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int ...

2025-03-21

0 42

题解 | 二叉搜索树的最近公共祖先来自专栏

搜索二叉树保存路径法保存路径找出最近公共祖先。找出公共祖先，临界情况分为，第一个不同点，p点，q点。递归函数是if-elseif-else结构，不需要显式return，返回正序顺序，所以先push_back再递归。 #include <vector> class Solution { p...

2025-03-18

0 86

题解 | 从上往下打印二叉树 JZ32 BFS

队列完成BFS判断根节点是否为空，非空，先进入队列中。判断出节点是否为空，非空，保持val值，左右子节点进入队列。队列弹出后，紧跟判断，为空停止循环 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *ri...

2025-03-18

0 68

题解 | 二叉树的镜像 JZ27 递归/分治

递归法根树的镜像可以转化成子树的镜像问题，终止条件是空节点返回空指针。从最小子树出发，核心是swap(pRoot->left,pRoot->right)，由根节点一路往下。不需要向上传递值，直接改变指针关系，返回值只在终止和返回根节点用到 TreeNode* Mirror(Tre...

2025-03-18

0 55

题解 | 二叉树的深度 JZ55 递归法来自专栏

递归法树的深度可以拆分成最大子树深度+1，直到子树为空。因此可以转变成递归问题递归技巧：不考虑函数内部实现，先考虑返回值。TreeDepth返回的是从该节点的开始的深度，因此TreeDepth(root->left)返回的是左子树高度，TreeDepth（root->right)返回的是...

2025-03-18

0 85