designeer

分类

面试指南(2) 题解(51)

/ 注册

全部文章（共51篇）

JZ79 平衡二叉树

题解解题思路一看到树的题目就要想到使用递归解决问题，而且有时候可以通过使用递归、遍历等框架解题。本题可以使用自顶向下的暴力法来遍历整棵树，时间复杂度相对较高也可以使用自底向上的递归，最关键就是要阻断递归，递归到一定情况要结束当前节点递归，降低时间复杂度方法一：...

Python2 Python3 二叉树

2021-11-06

1 544

JZ36 二叉搜索树与双向链表

思路： # 先中序遍历，将所有的节点保存到一个列表中。对这个list[:-1]进行遍历， # 每个节点的right设为下一个节点，下一个节点的left设为上一个节点。 class Solution: def&nbs...

Python2 Python3 二叉树

2021-11-06

8 798

JZ34 二叉树中和为某一值的路径(二)

1、采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。 2、我们也可以采用广度优先搜索的方式，遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。为了节省空间，我...

Python2 Python3 二叉树

2021-11-06

2 610

JZ82 二叉树中和为某一值的路径(一)

思路本题实质上是一道二叉树搜索的问题，通过遍历搜索二叉树，从而判断二叉树节点中是否存在节点和为指定值的路径。方法一：前序遍历这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。具体思路如下图所示： ...

Python2 Python3 二叉树

2021-11-06

5 796

JZ33 二叉搜索树的后序遍历序列

一、题目描述 JZ23 二叉搜索树的后序遍历序列题目大意：输入一个序列, 判断它是不是某二叉搜索树的后序遍历结果注意审题：假设输入序列的任意两个数字都互不相同且空树不是二叉搜索树二、算法1（分治）解题思路二叉树的后序遍历顺序是：左子树 -> 右子树 -&...

Python2 Python3 二叉树

2021-11-05

1 518

JZ32 从上往下打印二叉树

方法：层次遍历这道题就是一个模板题，对队列的使用。因为要满足先进先出的特性。初始化：一个队列queue<TreeNode*> q，将root节点入队列q 如果队列不空，做如下操作：弹出队列头，保存为node，将node的左右非空孩子加入队...

Python2 Python3 二叉树

2021-11-05

3 551

JZ27 二叉树的镜像

算法思想一：递归解题思路：根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。解题步骤： 1、特判：如果pRoot为空，返回空 2、交换左右子树 3、把pRoot的左子树放到Mirror中镜像一下 4、把pRo...

Python2 Python3 二叉树

2021-11-05

2 487

JZ26 树的子结构

算法思想一：递归解题思路： 1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归， 2.判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。 3.若pRoot2的节点不为null,并且pRoot...

Python2 Python3 树

2021-11-04

4 699

JZ8 二叉树的下一个结点

思路：两种情况：1）这个节点有右孩子，那下一个节点（根据中序遍历）肯定就是右孩子子树的最左边的叶节点；2）这个节点没有右孩子，那就往上走；如果这个节点是他父亲节点的左孩子，那就返回这个父亲节点；如果该节点是父亲节点的右孩子，那就一直往上走，直到...

Python2 Python3 二叉树

2021-11-03

5 586

JZ7 重建二叉树

递归： class Solution: def reConstructBinaryTree(self , pre: List[int], vin: List[int]) ...

Python2 Python3 二叉树

2021-11-03

4 550