华科不平凡

题解

/ 注册

全部文章 / 题解（共135篇）

二叉树的中序遍历（非递归）来自专栏

总结二叉树的非递归实现：先序遍历——采用栈和一个辅助指针，不断访问节点，并将左侧节点入栈，然后出栈访问右侧节点中序遍历——采用栈和一个辅助指针，将左侧节点入栈，然后访问中间节点，最后再入栈右侧节点后序遍历——最难的一个，采用栈和两个辅助指针，其中有一个辅助指针记录上一个访问的节点，如果是当...

二叉树中序遍历

2020-08-23

0 1115

构建二叉搜索树ii 来自专栏

后序遍历的变体，先将左右子树的所有搭配方式到两个vector，然后再用根节点分别与左右子树搭配： // // Created by jt on 2020/8/23. // #include <vector> using namespace std; class Solution { ...

后序遍历二叉树

2020-08-23

0 696

二叉搜索树的个数i 来自专栏

设值为n的情况下，可以组成f(n)个二叉搜索树，根据规律可知： f(0) = 1 f(1) = 1 f(n) += f(k-1)*f(n-k), 其中k=1,2,...n 显然，这是一个动态规划问题，实现如👇： // // Created by jt on 2020/8/23. // #inc...

二叉树二叉搜索树

2020-08-23

4 830

判断二叉搜索树来自专栏

利用后序遍历，如果左右子树均为二叉搜索树，且根节点与左右子树根节点的大小符合二叉树要求，则为整个树是二叉搜索树： // // Created by jt on 2020/8/23. // using namespace std; class Solution { public: /** ...

二叉树二叉搜索树

2020-08-23

1 781

恢复二叉搜索树来自专栏

二叉搜索树的中序遍历是有序的，如果二叉搜索树中两个节点被互换了，那么其中序遍历中必定有两个节点“错位”，因此中序遍历是解题的关键。中序遍历本身不难，但是题目要求常数级别的空间复杂度，因此想到了线索二叉树。总结下来两种思路: 空间复杂度为O(n)——线索二叉树空间复杂度为O(logn)——递归，...

递归二叉树中序遍历线索二叉树二叉搜索树

2020-08-23

1 825

判断二叉树是否对成来自专栏

两种方法：递归法——左子树与右子树比较、右子树与左子树比较（3ms + 504KB）迭代法——借助两个栈实现(3ms + 376KB) 递归 // // Created by jt on 2020/8/22. // using namespace std; class Solution ...

递归二叉树迭代

2020-08-22

4 704

二叉树的层序遍历来自专栏

用队列实现，每次记录下当前队列的大小即可： // // Created by jt on 2020/8/22. // #include <vector> #include <queue> using namespace std; class Solution { publi...

层序遍历二叉树

2020-08-22

63 7238

二叉树的之字层序遍历来自专栏

利用栈的特性，采用两个栈来实现：栈1，存放偶数层节点栈2，存放奇数层节点栈1出栈的时候，将下一层节点push到栈2，这样就实现了不断反转的效果。有一个至关重要的细节：对栈2出栈并将下一层节点推入栈1的过程中，需要先入右节点再入左节点，否则无法保证顺序。这个特性可以借助例子推导一下。 //...

层序遍历二叉树之字遍历

2020-08-22

20 1722

二叉树的最大深度来自专栏

本题有多种解法：后序遍历，每次返回以当前节点为根节点的子树的深度先序遍历，记录根节点到当前节点的高度，如果是叶子，则更新max值下面采用第一种思路： class Solution { public: /** * * @param root TreeNode类 ...

后序遍历二叉树

2020-08-22

15 1801

根据前序遍历和中序遍历构建二叉树来自专栏

采用先序遍历的思想构建即可。编码过程中，遇到了一个bug，只能通过25%的样例，反复检查逻辑问题，没有什么差错，最后面发现，原来是把第36行的==写成了=2333。总结：定位bug需要从多方面考虑：如果是样例通过不了：考虑算法思路是否有误、运算符是不是写错了如果是编译错误：考虑语法问题如果...

二叉树先序遍历

2020-08-22

0 784