心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #判断是不是完全二叉树#

利用层次遍历判断是否为完全二叉树层次遍历是从上到下，从左到右遍历，如果是完全二叉树，层次遍历的数组中出现null值的后面不应该再有节点值，因为完全二叉树叶子节点都在最左侧，因此可以在层次遍历中将null节点也加入队列，可以用一个布尔变量isComplete记录左边的节点是否为null，然后遇到nul...

2023-08-21

0 293

题解 | #合并二叉树#

纠正思路一开始是想将t2的节点全部都合并到t1，然后递归处理t1和t2的左子树的节点以及t1和t2右子树的节点，最后返回t1的根节点，但是这样处理t1为空t2不为空时，如果将t2的节点赋值给t1，就导致t1后面都有t2的节点了，而且t2节点为空时还会有空指针问题。正确做法应该是创建一个新的根节点，然...

2023-08-20

0 218

题解 | #对称的二叉树#

如何判断对称？二叉树对称说明左子树的左结点和右子树的右节点相同，以及左子树的右节点和右子树的左结点相同，因此可以将二叉树分成两半，分别递归遍历比较左子树的左结点和右子树的右节点，以及左子树的右节点和右子树的左结点。参考参考题解 import java.util.*; /* * public cl...

2023-08-20

0 190

题解 | #二叉搜索树与双向链表#

如何将二叉搜索树转换为双向链表？二叉搜索树的左子树节点小于当前节点，右子树节点均大于当前节点，二叉搜索树的中序遍历可以得到一个有序序列，问题在于怎么将树的节点转换为链表的节点，由于需要返回有序链表的头结点，因此需要一个head指针记录链表的最左节点，而链表的最左节点就是二叉树的左子树遍历的最左节点，...

2023-08-20

0 180

题解 | #二叉树中和为某一值的路径(一)#

递归分解问题题目要求根节点到叶子节点有没有等于sum值的路径，返回的是布尔值，因此可判断当前节点是否为叶子节点，如果是叶子节点就判断叶子节点的值是否为sum，如果不是则分解为子问题，即将sum减去当前值然后到左右子树中查找。题目返回的布尔值是自底向上从叶子节点依次返回的，即上一层的函数的返回值依赖于...

2023-08-20

0 187

题解 | #按之字形顺序打印二叉树#

基本思路难点在于不同层怎么按不同顺序打印节点值，不同层可以通过记录层数值判断是奇数层还是偶数层，打印节点值首先想的是如果偶数层就将队列中的下一层节点顺序反序，但是在for循环中加入下一层的节点一直是按左子树到右子树的顺序进行的，如果下一层节点的正确顺序为[5,7,9,11]，反转前队列中节点为[9,...

2023-08-19

0 264

题解 | #求二叉树的层序遍历#

基本思路难点在于怎么在遍历每一层时将该层的节点值加入到属于该层的列表中，一开始想到的是用栈保存节点，出栈时将节点值加入数组，再将该节点的子节点入栈，但是栈是先进后出的结构，不太符合从左到右的遍历顺序，而且不知道如何确定出栈时该节点属于哪一层。使用队列初始时保存根节点，节点出队将当前节点的值加入当前层...

2023-08-19

0 226

题解 | #寻找第K大#

快速排序跟二分查找解题快速排序是确定一个枢轴，然后将数组中大于枢轴的元素移动到枢轴左边，将数组中小于枢轴的元素移动到枢轴右边，然后在递归处理枢轴左右两边的元素。一般确定第一个元素为枢轴，然后用双指针法，一个指针从左到右遍历找小于枢轴的元素，另一个指针从右到左遍历找大于枢轴的元素，然后再交换这两个元素...

2023-08-18

0 301

题解 | #表达式求值#

双栈法解题需要维护一个操作数栈，一个操作符栈，一个操作符优先级的map。需要维护一个计算函数，操作符栈弹出一个操作和操作数栈弹出的两个操作数进行运算，运算结果再进入操作数栈。如果遇到数字则将该数字后面连着的数字都读取后拼接成完整的数字再进操作数栈。如果遇到操作符则先根据运算符优先级map，如果栈内运...

2023-08-18

0 301

题解 | #最小的K个数#

堆排序方法解题首先用数组的前k个元素构建一个包含k个元素的大顶堆，存储最小的k个数，再将数组后k个元素跟这个大顶堆的堆顶元素比较，如果小于堆顶元素，说明堆顶元素不是最小的k个数，因此将堆顶元素出堆，将当前元素入堆，堆中会重新排序，重复这样比较，最终堆中就包含了数组中最小的k个数。参考https://...

2023-08-18

0 314