youxiwang

题解

/ 注册

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

题解 | #二叉树的最小深度# [P3]

这题因为是找最浅的leaf node，明显BFS会更合适。那对于二叉树，BFS就是levelOrder traversal。找到第一个leaf就直接return当前深度。时间O(n) 空间O(n) import java.util.*; public class Solution { ...

Java

2022-01-23

0 350

题解 | JAVA #从下到上打印二叉树# [P3]

正常level-order traversal，每层到一个array里反向打印就用Linklist的descendingIterator, 或者用stack存每层的值就行。\ import java.util.*; public class Solution { public int[]...

Java

2022-01-23

1 461

题解 | JAVA #二叉树的最大宽度# [P3]

可以这样去给每一层的node编号： root = 0； root.left = root << 1; root.right = (root << 1) + 1; A 0 / \ ...

Java

2022-01-23

0 437

题解 | JAVA #判断是不是完全二叉树# [P0-T2]

跟这题一样的 https://blog.nowcoder.net/n/4012546b98ae4356ab926184ed323c58 import java.util.*; public class Solution { public boolean isCompleteTree (T...

Java

2022-01-23

9 1089

题解 | JAVA #二叉树的直径# [P3]

每个node的max直径是(leftTreeHeight + rightTreeHeight). 设个Gobal var存目前看到的最大diameter. dfs返回当前node为root的treeHeight。 import java.util.*; public class Solution ...

Java

2022-01-23

0 374

题解 | JAVA #二叉搜索树的最近公共祖先# [P2]

利用search tree的性质，在每个node上其实已经知道p和q分别在哪个child subtree。对于一个node，以下三种情况可以直接确定该node就是LCA. left里有一个target，root本身是一个target right里有一个target, root本身是一个target...

Java

2022-01-23

1 576

题解 | JAVA #输出二叉树的右视图# [P2]

跟精华解法里第二个HashMap的一样思路 JAVA版类似于用preOrder和inOrder重构一个right-first-preOrder traversal. https://blog.nowcoder.net/n/983254e186b2484c855622e68136bbc6 在re...

Java

2022-01-23

0 491

题解 | JAVA 先序 Scanner #序列化二叉树# [P1]

整体思路 - serialize和deserialize都用先序遍历实现题目里的例子：先序遍历就用标准recursion，null用#表示，node用“|"分割： visit(root); recurse(left); recurse(right); serialize结果："1...

Java

2022-01-23

1 364

题解 | Java #判断一棵二叉树是否为搜索二叉树和完全二叉树# [P0-T2]

搜索二叉树: in-order traversal (iterative). 记录上一次visit的值 (lastPoped)。没次visit只要check值是不是小于lastPoped. 相同解法也可以用recursion实现，但是需要把lastPoped存成global。完全二叉树: lev...

Java

2022-01-22

0 973

题解 | JAVA 分治 #重建二叉树# [P0]

递归, 分治跟精华解法一样思路，通过preOrder找root，inOrder找左右subtree的size. 唯一不一样的就是用HashMap存inOrder的[val -> index]。这样跑起来快很多。时间 O(n): 每个node都会call一次build() 空间 O(n):...

Java 分治递归二叉树

2022-01-21

1 475