designeer

题解

面试指南(2)

/ 注册

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

JZ68 在二叉树中找到两个节点的最近公共祖先

基于公共祖先特点的递归做法从根节点往下递归： 1. 若该节点是第一个值为o1或o2的节点，则该节点是最近公共祖先； 2. 否则，看左子树是否包含o1或o2： 2.1 若左子树包含o1或o2，则看右子树有没有： &nb...

Python2 Python3 二叉树

2021-11-08

4 679

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

import sys sys.setrecursionlimit(100000) class Solution: def __init__(self): &nbs...

Python2 Python3 二叉树

2021-11-07

1 628

JZ37 序列化二叉树

思路题目分析题目给出我们一棵树，要求我们实现两个函数第一个函数要求我们以任意遍历方式返回一个字符串第二个函数要求我们可以从上一个字符串中重新返回这棵树方法一：递归 ...

Python2 Python3 二叉树

2021-11-07

1 478

JZ78 把二叉树打印成多行

思路:用两个列表分别保存当前层节点和下一层节点，结果.append([i.val for i in 当前层节点]),然后当前层列表,下一层列表 = 下一层列表, [] 即可，直到当前层为空 class Solution: # 返...

Python2 Python3 二叉树

2021-11-07

1 452

JZ28 对称的二叉树

基本思想首先要明确，题目所定义的 “对称” 是对每层而言，同时考虑空节点。因此，如果我们使用常规的遍历方式进行检查的话，需要对空节点有所表示。局部检查（层序遍历）我们使用 0x3f3f3f3f 作为无效值，并建立占位节点 emptyN...

Python2 Python3 二叉树

2021-11-06

2 554

JZ79 平衡二叉树

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

Python2 Python3 二叉树

2021-11-06

1 536

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