甲乙小朋友的房子

甲乙小朋友很笨,但甲乙小朋友不会放弃

0%

算法-二叉树与分治

一些题目 implement of ....

时间复杂度训练

复习:

\[T(n) = T(\frac{n}{2}) + O(1) → O(logn)\]

\[T(n) = T(\frac{n}{2}) + O(n) → O(n)\]

** 问题1**

通过O(1)的时间,把n的问题,变为了两个n/2的问题,复杂度是多少?

\[T(n) = 2T(\frac{n}{2}) + O(1) → O(n)\]

解决:树型分析法

1
2
3
4
5
6
7
8
9
           n
/ \ --> 本次拆分耗费了O(1)的时间
n/2 n/2
/ \ / \ --> 本次拆分耗费了O(2)的时间
n/4 n/4 n/4 n/4
.....................
第k+1层 --> 本次拆分耗费了O(2^k)的时间
..................... --> 本次拆分耗费了O(n/2)的时间

总复杂度:

\[O(1+2+4+....+2^k+...+\frac{n}{2})\tag{1}\]

\(2^m = \frac{n}{2}\),则\(m=log(\frac{n}{2})=logn-log2=logn\)

则公式(1)等于:

\[O(2^0+2^1+2^2+....+2^{logn})\]

\[=O(\frac{a_1(1-q^n)}{1-q})=O(\frac{1-2^{logn}}{2-1})=O(n)\tag{结果}\]

问题2

\[T(n) = 2T(\frac{n}{2}) + O(n) =?\]

1
2
3
4
5
6
7
8
9
           n
/ \ --> 本次拆分耗费了O(n)的时间
n/2 n/2
/ \ / \ --> 本次拆分耗费了O(n)的时间
n/4 n/4 n/4 n/4
.....................
第k+1层 --> 本次拆分耗费了O(n)的时间
..................... --> 本次拆分耗费了O(n)的时间

总复杂度:

\[O(n+n+...+n)----logn次 = O(nlog(n))\tag{结果}\]

样例问题:mergeSort,就是这个复杂度!

二叉树的遍历

  • 前序遍历 - 先root
  • 中序遍历-中间是root
  • 后续遍历-最后root

二叉树的三种遍历,均由根节点开始,且路线是一样的,只不过节点访问的顺序不一样 .这条路线从根节点开始,沿着左子树深入下去,当深入到最左端,无法再深入下去返回

刚才深入时遇到的节点,再逐一进入其右子树,进行如此的深入和返回,直到最后从根 的右子树的返回根节点为止

在这一过程中,返回节点的顺序和进入节点的顺序相反,因此即先进入后返回,这一特 性正好符合栈后进先出的特点,因此三种遍历的非递归实现可以借助栈来实现: 在沿着左子树深入时,进入一个节点就将其压栈。

若是先序遍历,则在进栈之前访问之, 当沿左分支深入不下去时,则返回,即从栈中弹出前面压入的节点。

若为中序遍历,则 此时访问该节点,然后从该节点的右子树继续深入;若为后序遍历,则将此节点二次入 栈,然后从该节点的右子树继续深入,与前面类似,仍为进入一个节点入栈一个节点, 深入不下去时返回,直到第二次从栈里弹出该节点,才访问之

非递归实现

整体思路

因为要在遍历完节点的左子树后接着遍历节点的右子树,为了能找到该节点,需要使用来进行暂存。中序和后序也都涉及到回溯,所以都需要用到

三道题的解决思路可统一,模板也极其相似:

  1. 将二叉树分为“左”(包括一路向左,经过的所有实际左+根)、“右”(包括实际的右)两种节点
  2. 使用同样的顺序将“左”节点入栈
  3. 从下到上,以此访问其的右子树,同时把右子树看成一颗完整的树,重复上面的步骤

比如{1,2,3},当cur位于节点1时,1、2属于“左”节点,3属于“右”节点。DFS的非递归实现本质上是在协调入栈、出栈和访问,三种操作的顺序。上述统一使得我们不再需要关注入栈顺序,仅需要关注出栈和访问(第3点),随着更详细的分析,你将更加体会到这种简化带来的好处。

针对上述逻辑我们可以抽象出一个遍历规则,如下图所示:

即上面说到的三个步骤!

  1. 将二叉树分为“左”(包括一路向左,经过的所有实际左+根)、“右”(包括实际的右)两种节点
  2. 使用同样的顺序将“左”节点入栈
  3. 从下到上,以此访问其的右子树,同时把右子树看成一颗完整的树,重复上面的步骤

二叉树的遍历

前序

先序和中序的情况是极其相似的。

  • 先序的实际顺序:【根左】【右】
  • 中序的实际顺序:【左根】【右】

使用上述思路,先序和中序的遍历顺序可统一为:【“左”“右”】。

给我们的直观感觉是代码也会比较相似。实际情况正是如此,先序与中序的区别只在于对“左”节点的访问上。

非递归实现1

不需要入栈,每次遍历到“左”节点,立即输出即可。

需要注意的是,遍历到最左下的节点时,实际上输出的已经不再是实际的根节点,而是实际的左节点。这符合先序的定义。

1
2
3
4
5
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}

而后,因为我们已经访问过所有“左”节点,现在只需要将这些没用的节点出栈,然后转向到“右”节点。于是“右”节点也变成了“左”节点,后续处理同上。

1
2
3
4
5
if (!stack.empty()) {
cur = stack.pop();
// 把右子树作为一颗树,重复上面的步骤
cur = cur.right;
}

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private List<Integer> dfsPreOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();

TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}
if (!stack.empty()) {
cur = stack.pop();
// 把右子树作为一颗树,重复上面的步骤
cur = cur.right;
}
}

return results;
}

递归实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//调用主函数
public ArrayList<Integer> preorderTraversal(TreeNode root){
ArrayList<Integer> result = new ArrayList<Integer>();
traverse(root,result);
return result;
}
//递归定义:把root为根的preorder加入到result里
private void traverse(TreeNode root, ArrayList<Integer> result){
//停止条件
if( root == null ){
return;
}
//拆分问题
result.add(root.val);
traverse(root.left,result);
traverse(root.right,result);
}


递归

定义: 把root为根的preorder加入到result里

拆分问题: 放root,放left,放right

停止条件: root == null

递归实现2,分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> preorderTraversal(TreeNode root){
ArrayList<Integer> result = new ArrayList<Integer>();
// null or leaf
if( null == root ){
return result;
}
//分解问题
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);

//合并问题
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}

递归可能爆栈!

Binary Tree Preorder Traversal

实现二叉树的前序遍历

这道题除了以上说的递归和非递归的两种方式,还有另一种非递归的实现方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
list<Integer> preorder = new ArrayList<>();
if( null == root ){
return preorder;
}
stack.push(root);
while( !stack.empty() ){
TreeNode node = stack.pop();
preorder.add( node.val );
if( node.right != null ){
stack.push(node.right);
}
if( node.left != null ){
stack.push(node.left);
}
}
return preorder;
}

Flatten Binary Tree to Linked List

将二叉树按照前序遍历的顺序变为一颗只有右孩子的单链表

方法1,栈

思路:整体思路就是按照前序遍历的方式.

非递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void flatten(TreeNode root) {
if(root == null) return;
// 其实就是前序遍历
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
//stack.push(node);
TreeNode last = node;

while (!stack.isEmpty() || node != null){

while (node != null){
//System.out.println(node.val);
if(node.right != null) {
stack.push(node.right); // 这里只push进去node.right(因为后期只会使用到node.right)
}
if(node.left != null) {// 将左孩子挪到右孩子上
node.right = node.left;
TreeNode left = node.left;
node.left = null;
node = left;
}else {
break;
}
last = node;
}
if(stack.empty()) return;
node = stack.pop();
last.right = node; // 当前节点的右孩子应该是上一轮的最后一个孩子
last = node;
}
}

递归的另一种实现

自己写的实在是太糟糕了。我们看看九章的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1. 分别将右子树、左子树入栈
2. 本节点的新right就是栈顶的东西哇

public void flatten(TreeNode root) {
if(root == null) return;

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.empty()){
TreeNode node = stack.pop();
if(node.right != null) stack.push(node.right);
if(node.left != null) stack.push(node.left);

// 连接
node.left = null;
if(stack.empty()) node.right = null;
else node.right = stack.peek();
}
}

方法2,分治

这道题的递归方式我是死活都没写出来。其实就是向右探到底那没想通。哎

假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了:

1
2
3
4
5
6
7
8

1
/ \
2 5
\ \
3 6 <- rightLast
\
4 <- leftLast

如何将root、T(root->left)、T(root->right) flatten成一整个linked list?显而易见:

1
2
3
4
temp = root.right
root.right = root.left
root.left = NULL
leftTail.right = temp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void flatten(TreeNode root) {
helper(root);
}

// flatten root and return the last node
private TreeNode helper(TreeNode root) {
if (root == null) {
return null;
}

TreeNode leftLast = helper(root.left);
TreeNode rightLast = helper(root.right);

// connect leftLast to root.right
if (leftLast != null) {
leftLast.right = root.right;
root.right = root.left;
root.left = null;
}

if (rightLast != null) {
return rightLast;
}

if (leftLast != null) {
return leftLast;
}

return root;
}

参考Grandyang

Verify Preorder Serialization of a Binary Tree,331

验证一个序列是否是二叉树的前序遍历。例如给出"9,3,4,#,#,1,#,#,2,#,6,#,#",它是某一个树(示意图如下)的前序遍历,那就输出true。

1
2
3
4
5
6
7
     _9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int visitedCount = 0;
int idx = 0;
private void helper(String[] preoders){

if(idx >= preoders.length) return;
++visitedCount;
// 访问根节点
//System.out.println(preoders[idx]);
if(!Character.isDigit(preoders[idx].charAt(0))) return;
// 访问左节点
++idx;
helper(preoders);
++idx;
// 访问右节点
helper(preoders);
}

public boolean isValidSerialization(String preorder) {
String[] preorders = preorder.split(",");
if(preorders.length == 1 && preorders[0].charAt(0) == '#') return true;
if(preorders.length % 2 == 0 || preorders.length < 3) return false;
helper(preorders);
return visitedCount == preorders.length;
}

中序

基于对先序的分析,先序与中序的区别只在于对“左”节点的处理上,我们调整一行代码即可完成中序遍历。

1
2
3
4
5
6
7
8
9
10
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
if (!stack.empty()) {
cur = stack.pop();
results.add(cur.val); // 仅调整该行代码
// 把右子树作为一颗树,重复上面的步骤
cur = cur.right;
}

注意,我们在出栈之后才访问这个节点。因为先序先访问实际根,后访问实际左,而中序恰好相反。相同的是,访问完根+左子树(先序)或左子树+根(中序)后,都需要转向到“右”节点,使“右”节点称为新的“左”节点。

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private List<Integer> dfsInOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();

TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
if (!stack.empty()) {
cur = stack.pop();
results.add(cur.val);
// 把右子树作为一颗树,重复上面的步骤
cur = cur.right;
}
}
return results;
}

Binary Tree Inorder Traversal

实现二叉树的中序遍历

Minimum Absolute Difference in BST

给一个二叉搜索树。求任意两个结点之间绝对值的最小值。

思路:中序遍历,用后面的减去前面的,找到最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
int last = -1;
int min = Integer.MAX_VALUE;
while (!stack.isEmpty() || null != root){
while (null != root) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(last == -1){last = root.val;}
else{
min = Math.min(min,root.val - last);
last = root.val;
}
root = root.right;
}
return min;
}

Kth Smallest Element in a BST

输出搜索二叉树第k小的数

BST的中序遍历是从小到大的。因此只需要按照中序遍历输出第k个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int kthSmallest(TreeNode root, int k) {
if(null == root) return -1;
Stack<TreeNode> stack = new Stack<>();
int i = 0;
while (!stack.isEmpty() || null != root){
while (null != root){
stack.push(root);
root = root.left;
}
root = stack.pop();
i++;
if(i == k){
return root.val;
}
root = root.right;
}
return -1;
}

递归写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int count=0;
int ans=0;
int flag=0;
void inorder(TreeNode node,int k){
if(node==null){
return ;
}
inorder(node.left,k);
count++;
ans=node.val;
if(count==k){
flag=ans;
}
inorder(node.right,k);
}
public int kthSmallest(TreeNode root, int k) {
inorder(root,k);
return flag;
}

后序

后序的情况略有不同,但仍然十分简洁。

  • 后序的实际顺序:左右根

入栈顺序不变,我们只需要考虑第3点的变化。出栈的对象一定都是“左”节点(“右”节点会在转向后称为“左”节点,然后入栈),也就是实际的左或根;实际的左可以当做左右子树都为null的根,所以我们只需要分析实际的根。

对于实际的根,需要保证先后访问了左子树、右子树之后,才能访问根。实际的右节点、左节点、根节点都会成为“左”节点入栈,所以我们只需要在出栈之前,将该节点视作实际的根节点,并检查其右子树是否已被访问即可。如果不存在右子树,或右子树已被访问了,那么可以访问根节点,出栈,并不需要转向;如果还没有访问,就转向,使其“右”节点成为“左”节点,等着它先被访问之后,再来访问根节点。

所以,我们需要增加一个标志,记录右子树的访问情况。由于访问根节点前,一定先紧挨着访问了其右子树,所以我们只需要一个标志位。

完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null){
return result;
}

Stack<TreeNode> stack = new Stack<TreeNode>();
HashSet<TreeNode> flag = new HashSet<TreeNode>();
TreeNode curr = root;
while (stack.size() > 0 || curr != null){
while(curr != null){
stack.push(curr);
curr = curr.left;
}

if (stack.size() > 0){
curr = stack.peek();
if (!flag.contains(curr)){
// 说明curr.right还没有被访问过。所以先不弹出它
flag.add(curr);
curr = curr.right;
}else{
// 说明curr.right已经被访问过了。那就可以弹出&访问curr了
result.add(curr.val);
stack.pop();
curr = null; // 不需要转向了,继续弹!
}
}
}

return result;
}

Binary Tree Postorder Traversal,145

实现二叉树的后序遍历

这道题除了以上说的递归和非递归的两种方式,还有一种更骚气的,利用双栈。

但实际上它做的是反向的先序遍历。亦即遍历的顺序是:节点 -> 右子树 -> 左子树。这生成的是后根遍历的逆序输出。使用第二个栈,再执行一次反向输出即可得到所要的结果。

下面是它的实现步骤:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
将根节点压入第一个栈
从第一个栈中弹出一个元素,压入第二个栈
然后分别将该节点的左右孩子压入第一个栈
重复步骤2和步骤3直到第一个栈为空
执行结束,第二个栈中就保存了所有节点的后序遍历输出结果。依次将元素从第二个栈中弹出即可。

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}

Stack<TreeNode> tmp = new Stack<>();
Stack<TreeNode> out = new Stack<>();

tmp.push(root);

while (!tmp.isEmpty()) {
TreeNode node = tmp.pop();
out.push(node);

if (node.left != null) {
tmp.push(node.left);
}

if (node.right != null) {
tmp.push(node.right);
}
}

while (!out.isEmpty()) {
result.add(out.pop().val);
}
return result;
}

或者用root->right->left,然后用链表addFirst反转结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
if (root == null){
return result;
}

Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while (stack.size() > 0 || curr != null){
while(curr != null){
result.addFirst(curr.val);
stack.push(curr);
curr = curr.right; // right!
}

if (stack.size() > 0){
curr = stack.pop();
curr = curr.left; // left!
}
}

return result;
}

Subtree of Another Tree,572

给两个二叉树s和t。判断t是否是s的子树

思路一,非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
private boolean check(TreeNode s_in,TreeNode t_in){
TreeNode t = t_in;
TreeNode s = s_in;
Stack<TreeNode> stack_t = new Stack<>();
Stack<TreeNode> stack_s = new Stack<>();
while (!stack_t.isEmpty()|| null != t){
while (null != t && null != s){
stack_t.push(t);
stack_s.push(s);
s = s.left;
t = t.left;
}
if(!( (null != t && null != s)||
(null == t && null == s)) ) return false;
t = stack_t.pop();
s = stack_s.pop();
if(t.val != s.val){
return false;
}
s = s.right;
t = t.right;
if(!( (null != t && null != s)||
(null == t && null == s)) ) return false;
}
return true;
}
public boolean isSubtree(TreeNode s, TreeNode t) {
// 从s里找t
// 遍历s
if(null == t) return true;
if(null == s) return false;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || null != s){
while (null != s){
stack.push(s);
s = s.left;
}
s = stack.pop();
if(s.val == t.val){
if(check(s,t)) return true;
}
s = s.right;
}
return false;
}

思路二,递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean check(TreeNode s, TreeNode t){
if(null == s && null == t) return true;
if(null == s || null == t) return false;
if(s.val == t.val){
return check(s.left,t.left) && check(s.right,t.right);
}else{
return false;
}
}
public boolean isSubtree(TreeNode s, TreeNode t) {
// 从s里找t
// 遍历s
if(null == t || null == s) return false;
if(s.val == t.val){
if(check(s,t))return true;
}
return isSubtree(s.left,t) || isSubtree(s.right,t);
}

Construct Binary Tree from Preorder and Inorder Traversal

用前序+中序恢复二叉树

Construct Binary Tree from Inorder and Postorder Traversal,106

用中序+后序恢复二叉树

思路:

  • 中序遍历:左 + 根 + 右
  • 后序遍历:左 + 右 + 跟

因此后序遍历可以直接确定根节点;然后去中序里面找根节点。找到根节点后,就可以确定左右子树的大小。那么就可以继续递归了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0) return null;
return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode helper(int[] inorder, int inLow, int inHigh, int[] postorder, int postLow, int postHigh){
// 中序遍历:左 + 根 + 右
// 后序遍历:左 + 右 + 跟
if(inLow > inHigh || postLow > postHigh) return null;
TreeNode root = new TreeNode(postorder[postHigh]);
if(postLow == postHigh) return root;
//System.out.println(inLow + "\t" + inHigh + "\t" + postLow + "\t" + postHigh);
// 从中序遍历中寻找根节点的idx
int rootIdx = inLow;
for(rootIdx = inLow; rootIdx <= inHigh; ++rootIdx){
// 这里其实可以用hashmap优化
if(inorder[rootIdx] == postorder[postHigh])break;
}
int leftNum = rootIdx - inLow;
root.left = helper(inorder, inLow, rootIdx - 1, postorder, postLow, postLow + leftNum - 1);
root.right = helper(inorder, rootIdx + 1, inHigh, postorder, postLow + leftNum, postHigh - 1);
return root;
}

DFS

DFS有两种实现方式:

  • 非递归
  • 递归 -- 有两种选择:
    • 分治
    • 遍历

碰到二叉树问题,就想想整棵树上在该问题上的结果是什么,左右儿子在该问题上的结果之间的联系是什么

Symmetric Tree,101

验证一个二叉树是否是镜像的

思路就是分成两路探索,一路左边,一路右边。

1
2
3
4
5
6
7
8
9
10
11
private boolean helper(TreeNode leftBranch, TreeNode rightBranch){
if(leftBranch == null && rightBranch == null) return true;
if(leftBranch == null || rightBranch == null) return false;
return (leftBranch.val == rightBranch.val) &&
helper(leftBranch.left, rightBranch.right)&&
helper(leftBranch.right, rightBranch.left);
}
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return helper(root.left, root.right);
}

Path Sum

给一个二叉树和一个target。求二叉树的某个路径和是否完全等于target。

基础题:Binary Tree Paths,可以考虑先做这个基础题,然后在做这些

思路:递归就好

1
2
3
4
5
6
7
8
9
10
private boolean helper(TreeNode node, int sum, int target){
if(node.left == null && node.right == null) return sum == target;
return (node.left != null && helper(node.left, sum + node.left.val, target) ||
node.right != null && helper(node.right, sum + node.right.val, target));

}
public boolean hasPathSum(TreeNode root, int target) {
if(root == null) return false;
return helper( root, root.val, target);
}

Path Sum II

给一个二叉树和一个target。求二叉树的路径和完全等于target的所有路径

还是递归哇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<List<Integer>> result = new LinkedList<>();
private void helper(TreeNode node, int sum, List<Integer> list, int target){
if(node.left == null && node.right == null){
if(sum == target){result.add(new ArrayList<>(list));}
return;
}
if(node.left != null){
list.add(node.left.val);
helper(node.left, sum + node.left.val, list, target);
list.remove(list.size() - 1);
}
if(node.right != null){
list.add(node.right.val);
helper(node.right, sum + node.right.val, list, target);
list.remove(list.size() - 1);
}

}
public List<List<Integer>> pathSum(TreeNode root, int target) {
if(root != null){
List<Integer> lists = new LinkedList<Integer>();
lists.add(root.val);
helper(root, root.val,lists , target);
}
return result;
}

Path Sum III

给一个二叉树和一个target。求二叉树某点到其的某个子节点的和等于target的个数。

思路:其实这道题类似于单条路径上的这道题:560. Subarray Sum Equals K

在dfs时,存储当前节点i路径下的所有父节点j到root的和。那么sum[i,j] = sum[i] - sum[j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int counter = 0;
private void helper(TreeNode node, int[] sums, int level, int target){
// 先检查本节点是否存在于上面节点的和==target的情况
if(sums[level] == target) ++counter;
for(int i = 0; i < level; ++i){
// System.out.println(i + "\t" + (sums[level] - sums[i]));
if(sums[level] - sums[i] == target) ++counter;
}
// sum存储从根节点到本节点,每个节点的到root的和
if(node.left != null){
sums[level + 1] = sums[level] + node.left.val;
helper(node.left, sums, level + 1, target);
sums[level + 1] = 0;
}
if(node.right != null){
sums[level + 1] = sums[level] + node.right.val;
helper(node.right, sums, level + 1, target);
sums[level + 1] = 0;
}
}
public int pathSum(TreeNode root, int target) {
if(root == null) return 0;
int[] sums = new int[1001];
sums[0] = root.val;
helper(root, sums, 0, target );
return counter;
}

优化:所有和还可以用hash表存储!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int counter = 0;
private void helper(TreeNode node, HashMap<Integer, Integer> sums, int lastSum, int target){
// 检查与根节点
int thisSum = lastSum + node.val;
if(thisSum == target) ++counter;
//检查与其它节点
if(sums.containsKey(thisSum - target)) {
counter += sums.get(thisSum - target);
}
//将本节点加入
if(sums.containsKey(thisSum)){
sums.replace(thisSum, sums.get(thisSum) + 1);
}
else sums.put(thisSum, 1);
if(node.left != null){
helper(node.left, sums,thisSum, target);
}
if(node.right != null){
helper(node.right, sums, thisSum, target);
}
//将本节点挪出
if(sums.get(thisSum) > 1) sums.replace(thisSum, sums.get(thisSum) - 1);
else sums.remove(thisSum);
}
public int pathSum(TreeNode root, int target) {
if(root == null) return 0;
HashMap<Integer, Integer> sums = new HashMap<>();
helper(root, sums, 0, target );
return counter;
}

Trim a Binary Search Tree

修剪二叉树,使得值在[L,R] 之间。修剪时,优先保留左子树。

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root == null)return root;
if(root.val >= L && root.val <= R){
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
}else{
TreeNode left = trimBST(root.left, L, R);
if(null != left) root = left;
else root = trimBST(root.right, L, R);
}
return root;
}

BFS相关例题

BFS最重要的两个数据结构:

  • 队列
  • 哈希表

层序遍历

例题1,Binary Tree Level Order Traversal,102

队列!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(null == root){
return result;
}
// interface
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size =queue.size();
ArrayList<Integer> currentLevel = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode head = queue.poll();
currentLevel.add(head.val);
if(head.left != null){
queue.offer(head.left);
}
if(head.right != null){
queue.offer(head.right);
}
}
result.add(currentLevel);
}
return result;

Binary Tree Level Order Traversal II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> result = new LinkedList<>();
// LinkedList是List接口的实现,所以可以直接使用
if(null == root) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> curResult = new LinkedList<>();
while (size > 0){
TreeNode cur = queue.poll();
curResult.add(cur.val);
if(null != cur.left){
queue.offer(cur.left);
}
if(null != cur.right){
queue.offer(cur.right);
}
--size;
}
result.addFirst(curResult); // 注意这个神奇的东西
}
return result;
}

Binary Tree Zigzag Level Order Traversal,103

输出二叉树的层序遍历,且需要隔层倒序。

思路:用一个linkedList就好啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if(null == root) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean fromHead = false;
while (!queue.isEmpty()){
int size =queue.size();
LinkedList<Integer> oneResult = new LinkedList<>();
while (size > 0){
TreeNode now = queue.poll();
if(fromHead){
oneResult.addFirst(now.val);
}else {
oneResult.addLast(now.val);
}
if(null != now.left) queue.offer(now.left);
if(null != now.right)queue.offer(now.right);
--size;
}
fromHead = !fromHead;
result.add(oneResult);
}
return result;
}

思路2:用两个栈,单数层先left后right,双数层先right后left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
// currLevel表示当前在处理的那一层的结点
// nextLevel表示下一层要处理的结点
Stack<TreeNode> currLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
Stack<TreeNode> tmp;

currLevel.push(root);
boolean normalOrder = true;

while (!currLevel.isEmpty()) {
ArrayList<Integer> currLevelResult = new ArrayList<Integer>();

while (!currLevel.isEmpty()) {
TreeNode node = currLevel.pop();
currLevelResult.add(node.val);

if (normalOrder) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
} else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
}
result.add(currLevelResult);
// 交换currLevel和nextLevel,currLevel代表将要处理的那一层结点
tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;

normalOrder = !normalOrder;
}

}

Binary Tree Right Side View,199

给一个二叉树。从最右边看去,能看到的数字都是几?

思路:层序遍历,输出每层的最后一个元素!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new LinkedList<>();
if(root == null) return result;
// 层序遍历的最后一个
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
TreeNode temp = null;
while (size > 0){
temp = queue.poll();
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
--size;
}
result.add(temp.val);
}
return result;
}

Populating Next Right Pointers in Each Node I 和II

给一个二叉树,每个节点应该有一个兄弟节点,但输入前兄弟节点还是空的。完成一个函数实现它。

思路一:层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void connect(TreeLinkNode root) {
if(root == null) return;
Queue<TreeLinkNode> level = new LinkedList<>();
level.add(root);
while (!level.isEmpty()){
int size = level.size();
TreeLinkNode last = null;
while (size-- > 0){
TreeLinkNode curr = level.poll();
if(curr.left != null)level.add(curr.left);
if(curr.right != null)level.add(curr.right);
if(last == null){
last = curr;
continue;
}else {
last.next = curr;
last = curr;
}
}
}
}

思路2,骚操作 —— 只适合I,不适合II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 满二叉树!
node next
/ \ / \
left right left right

node.right.next = node.next.left !!!!!

public void connect(TreeLinkNode root) {
while (null != root){
TreeLinkNode cur = root;
while (cur != null){
if(cur.left != null)cur.left.next = cur.right;
if(cur.right != null && cur.next != null) cur.right.next = cur.next.left;
cur = cur.next;
}
root = root.left;
}
}

Minimum Depth of Binary Tree,111

返回二叉树叶子结点的最小的层数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minDepth(TreeNode root) {
if(null == root) return 0;
Queue<TreeNode> queue = new LinkedList<>();
int level = 1;
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
TreeNode now = queue.poll();
if(null == now.right && null == now.left) return level;
if(null != now.left) {queue.offer(now.left);}
if(null != now.right) {queue.offer(now.right);}
--size;
}
++level;
}
return level;
}

Find Largest Value in Each Tree Row

输出二叉树每行的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new LinkedList<>();
if(root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
int max = Integer.MIN_VALUE;
while (size > 0){
root = queue.poll();
max = Math.max(max, root.val);
if(root.left != null) queue.add(root.left);
if(root.right != null) queue.add(root.right);
--size;
}
result.add(max);
}
return result;
}

01 Matrix

给一个矩阵。将这个矩阵变为:每个元素的值=它与最近的0的距离

这个操作还是第一次遇到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[][] updateMatrix(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0)return matrix;
int m = matrix.length;
int n = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
// 队列维护当前已确定的方格
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(matrix[i][j] == 0) queue.add(new int[]{i,j});
else matrix[i][j] = Integer.MAX_VALUE;
}
}
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
while (!queue.isEmpty()){
int[] pair = queue.poll();
for(int k = 0; k < 4; ++k){
if(matrix[pair[0]+dx[k]][pair[1]+dy[k]] < matrix[pair[0]][pair[1]] + 1) continue;
matrix[pair[0]+dx[k]][pair[1]+dy[k]] = matrix[pair[0]][pair[1]] + 1;
queue.add(new int[]{pair[0]+dx[k],pair[1]+dy[k] });
}
}
return matrix;
}

Word Ladder

输入的是:一个单词和一个字典,单词每次只允许改变一个字母变成字典中的某个单词,如此循环,判断是否能变成目标单词,如果能的话返回变换次数,否则返回0。

  1. 将每个单词看成图的一个节点。
  2. 当单词s1改变一个字符可以变成存在于字典的单词s2时,则s1与s2之间有连接。
  3. 给定s1和s2,问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

无论是求最短路径长度还是求所有最短路径,都是用BFS。在BFS中有三个关键步骤需要实现:

  1. 如何找到与当前节点相邻的所有节点。 这里可以有两个策略:
  1. 遍历整个字典,将其中每个单词与当前单词比较,判断是否只差一个字符。复杂度为:n*w,n为字典中的单词数量,w为单词长度。
  2. 遍历当前单词的每个字符x,将其改变成a~z中除x外的任意一个,形成一个新的单词,在字典中判断是否存在。复杂度为:26*w,w为单词长度。 这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说,长度大多小于100,而字典中的单词数则往往是成千上万,所以策略2相对较优。
  1. 如何标记一个节点已经被访问过,以避免重复访问。 可以将访问过的单词从字典中删除。
  2. 一旦BFS找到目标单词,如何backtracking找回路径?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
这道题写了有五六个小时。气死了。


private int hammin(String a, String b){
int dist = 0;
for(int i = 0; i < a.length(); ++i){
if(a.charAt(i) == b.charAt(i)) continue;
++dist;
if(dist > 2) break;
}
return dist;
}
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if(beginWord.equals(endWord)) return 0;
boolean[] visited = new boolean[wordList.size()];
// 层序遍历
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
int level = 1;
while (!queue.isEmpty()){
++level;
int size = queue.size();
while (size-- > 0){
String currKey = queue.poll();
// 将所有汉明距离为1的字符加入
int i = 0;
for(String s : wordList){
if(!visited[i] && hammin(currKey, s) == 1){
visited[i] = true;
queue.add(s);
if(s.equals(endWord)) return level;
}
++i;
}
}
}
return 0;
}

Minimum Height Trees

给一个无向无环图,求一个节点,使得它到任何点的距离最短。

非常巧妙的思路。从叶子结点开始BFS,每次删掉一层的叶子结点。最后剩的那一层就是结果!

一开始我只想到了半截,没有想到用队列,而是想到用优先队列。也没想通最后一层就是结果。难受。最后参考了他的代码 才想通了这些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Node{
int idx;
List<Integer> neibors;
int degree = 0;
Node(int idx){
this.idx = idx;
neibors = new LinkedList<>();
}
}

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// 寻找根节点

Node[] nodes = new Node[n];
for(int i = 0; i < n; ++i){
nodes[i] = new Node(i);
}
for(int[] edge : edges){
nodes[edge[0]].neibors.add(edge[1]);
nodes[edge[1]].neibors.add(edge[0]);
++nodes[edge[0]].degree;
++nodes[edge[1]].degree;
}
// 根节点: acCounter == 1 的节点
Queue<Integer> queue = new LinkedList<>(); // 存放根节点,这一点一开始没有想到
for(int i = 0; i < n; ++i){
if(nodes[i].degree == 1) queue.add(i);
}
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()){
result = new ArrayList<>();// 这一步非常巧妙,因为每次BFS的叶子结点的对外层数都相等!
// BFS删除所有的根节点
int size = queue.size();
while (size > 0) {
--size;
result.add(queue.peek());
Node root = nodes[queue.poll()];
// 删除这个根节点的边
for (int neibor : root.neibors) {
--nodes[neibor].degree;
--root.degree;
if (nodes[neibor].degree == 1) {
queue.add(neibor);
}
}
}
}
return result;
}

分治相关例题

例题1,Maximum Depth of Binary Tree

求二叉树的最大深度

方法一,遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

private int max = 0;

//从root出发,root当前深度是1
helper(root,1);

private void helper(TreeNode root, int depth){
//走过头了
if( root == null ){
return;
}
max = Math.max(max,depth);
helper(root.left, depth + 1 );
helper(root.right, depth + 1 )
}

方法2,分治

没有全局变量

1
2
3
4
5
6
7
8
9
public int maxDepth(TreeNode root){
if( root == null ){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);

return Math.max(leftDepth,rightDepth) + 1;
}

例题2,Balanced Binary Tree

判断一个树是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//当一个结果有多个参数决定时,定义一个class
class ResultType{
public boolean isBalanced;
public int maxDepth;
public ResultType(boolean isBalanced, int maxDepth){
this.isBalanced = isBalanced;
this.maxDepth = maxDepth;
}
}

// 主函数
public boolean isBalanced(TreeNode root){
return helper(root).isBalanced;
}
// 分治
private ResultType helper(TreeNode root){
if(null == root){
return new ResultType(true,0);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);

// 子树不平衡
if(!left.isBalanced || !right.isBalanced){
return new ResultType(false,-1);
}
// root不平衡
if(Math.abs(left.maxDepth - right.maxDepth) > 1){
return new ResultType(false,-1);
}
return new ResultType(true,Math.max(left.maxDepth , right.maxDepth) + 1);
}

另一种解法:

1
2
3
4
5
6
7
8
9
10
11
12
public int helper(TreeNode root){
if(null == root) return 0;
int leftDepth = helper(root.left);
if(leftDepth == -1) return -1;
int rightDepth = helper(root.right);
if(rightDepth == -1) return -1;
if(Math.abs(leftDepth-rightDepth)>1)return -1;
return Math.max(leftDepth,rightDepth) + 1;
}
public boolean isBalanced(TreeNode root) {
return helper(root)!=-1;
}

例题3,Lowest Common Ancestor,236

求一颗二叉树中两个点a,b的最近公共祖先

在root为根的二叉树中,从上到下寻找A,B的LCA:

  • 如果找到了就返回这个LCA
  • 如果只碰到A,就返回A
  • 如果只碰到B,就返回B
  • 如果都没有,就返回null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode nodel1, TreeNode node2){
if(root == null || root == node1 || root == node2){
// 很有趣的点:如果root是node1,且root包含node2,那么此时别的node就不可能返回非null了。那么此时root肯定是了。
return root;
}
// 分解问题
TreeNode left = lowestCommonAncestor(root.left, node1, node2);
TreeNode right = lowestCommonAncestor(root.right, node1, node2);

// 合并问题
if(left != null && right != null){ // left中含有n1或n2,right也含有
return root;
}
if(right != null){ // right中含有n1或n2,left不含
return right;
}
if(left != null){ // left中含有n1或n2,right不含
return left;
}
return null;
}

另一种思路,统计本节点的子节点中有几个命中节点 如果等于两个,则本节点是公共祖先!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
TreeNode result;
public int helper(TreeNode root, TreeNode p,TreeNode q){
int counter = 0;
if( null == root || null != result) return counter;
if( root == p ) {
counter += 1;
}else if( root == q ) {
counter += 1;
}
if( counter == 2 ){
if(null == result)result = root;
return counter;
}
counter += helper(root.right,p,q);
if( counter == 2 ){
if(null == result)result = root;
return counter;
}
counter += helper(root.left,p,q);
if( counter == 2 ){
if(null == result)result = root;
return counter;
}

return counter;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

int counter = helper(root,p,q);
return result;
}

例题4,Lowest Common Ancestor II

1
2
3
4
5
在root为跟的二叉树中找n1,n2的LCA
如果找到了就返回
如果只碰到了n1,就返回n1
如果只碰到了n2,就返回n2
如果都没有,就返回Null

例题5,Binary Tree Maximum Path Sum II

给一个二叉树,找到从root的最大路径和。路径可以在任何地方被结束掉。

1
2
3
4
5
6
7
8
9
   1
/ \
2 3
\
-1

return 4

思路:某个点的最大长度 = Math.max(0,sum)

例题6,Binary Tree Maximum Path Sum,124

给一个二叉树,找到从any node 到 any node最大路径和。路径可以在任何地方被结束掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
  -1
/ \
2 3
\
-1

return 3

思路:两个分治

要求整个二叉树的最长路径,先求左子树的最长路径,再求右子树的最长路径。

整棵树的最长路径(以上图为例):
1. 有可能全在左边(只有2
2. 有可能全在右边(只有3
3. 可能跨过root节点(有-123

class ResultType{
int root2This, any2This;
ResultType(int root2This, int any2This){
this.root2This = root2This;
this.any2This = any2This;
}
}

private ResultType helper(TreeNode root){
// illegal
if(null == root){
return new ResultType(Integer.MIN_VALUE,Integer.MIN_VALUE);
}
// 分解问题
ResultType left = helper(root.left);
ResultType right = helper(root.right);

// 合并问题
// 为了方便之后的第3步计算(为了解决any2this,一定要算出root2this)
int root2This = Math.max(0,Math.max(left.root2This, right.root2This)) + root.val;

// 1、2. root到这个节点的最大sum
// 全在左边或者全在右边(可以不包含root)
int any2This = Math.max(left.any2This, right.any2This);
// 3. any到这个节点的最大sum
// 跨过了root点(一定是root到left或right的路径)
any2This = Math.max(any2This,
Math.max(0, left.root2This)
+ Math.max(0, right.root2This)
+ root.val);

return new Result(root2This, any2This);
}

代码:
// int[0] - > any 2 any
// int[1] --> end 2 this
public int[] helper(TreeNode node) {
if(null == node) return new int[]{-9999999,-9999999};
int[] left = helper(node.left);
int[] right = helper(node.right);
// 从本节点向下的某个节点截止
int down2This = Math.max(
Math.max(left[1] + node.val,
right[1] + node.val),
node.val
);
// 跨越node节点
int twoside = left[1] + node.val + right[1];
// 全在左子树或全在右子树
int oneside = Math.max(left[0],right[0]);
// 三者求最大
int any2This = Math.max(down2This,Math.max(oneside,twoside));
return new int[]{any2This,down2This};
}
public int maxPathSum(TreeNode root) {
return helper(root)[0];
}

还有一种骚操作,只记录【本节点】到【下方节点】的最大和!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int max = Integer.MIN_VALUE; // 全局最大
public int maxPathSum(TreeNode root) {
if(root == null) return 0;
traverse(root);
return max;
}

private int traverse(TreeNode root) {
if(root == null) return 0;
int left = traverse(root.left);
int right = traverse(root.right);
max = Math.max(max, Math.max(left, 0) + Math.max(right, 0) + root.val);
return Math.max(0, Math.max(left, right)) + root.val;
}

Invert Binary Tree,226

将二叉树镜像反转(左右替换)

1
2
3
4
5
6
7
8
public TreeNode invertTree(TreeNode root) {
if(root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}

二叉搜索树

BST定义

定义

  • 左子树比根节点小
  • 右子树比根节点大
    • 如果有重复,可以全部放在左/右

效果

  • 中序遍历是升序序列

性质

  • 如果一颗二叉树中序不是升序,则一定不是BST
  • 如果一颗二叉树中序是升序,则不一定是BST

删除

本节主要参考自:【算法导论】二叉搜索树的插入和删除

从一个二叉搜索树中删除一个结点,会有三种情况:

  • 如果z没有孩子节点,就直接删除,并修改它的父节点,用null作为它的孩子;

  • 如果z只有一个孩子,就将这个孩子提升到树中z的位置上,并修改z的父节点,用z的孩子来替换z;

  • 如果z有两个孩子,那么可以寻找节点的后继(中序遍历时的下一个结点)。删除方法如下:

    • 找到该节点的右子树中的最左孩子(也就是右子树中序遍历的第一个节点)
    • 把它的值和要删除的节点的值进行交换
    • 然后删除这个节点(其实就是用这个节点的右子树替换这个节点,因为这个节点此时已经肯定没有左子树了)

代码见后面的题- Delete Node in a BST

Validate Binary Search Tree,98

验证一个二叉树是不是搜索二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
BST有一个性质——如果一个二叉树的中序遍历是严格递增的,则这个二叉树一定是BST.

public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
long last = Long.MIN_VALUE;
while (!stack.isEmpty() || null != root){
while (null != root){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(last < root.val){
last = root.val;
}else {
return false;
}
root = root.right;
}
return true;
}

Binary search Tree Iterator,173

中序遍历。要一个给一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class BSTIterator {
Stack<TreeNode> stack;
TreeNode root;
public BSTIterator(TreeNode root) {
this.root = root;
stack= new Stack<>();
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
return!stack.isEmpty() || null != root;
}

/** @return the next smallest number */
public int next() {
while (null != root){
stack.push(root);
root = root.left;
}
root = stack.pop();
int result =root.val ;
root = root.right;
return result;
}
}

/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/

Convert Sorted Array to Binary Search Tree

将有序数组转化为平衡二叉树

思路:平衡二叉树的root一定是有序数组的中点!

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode helper(int[] nums, int start, int end){
if(end < start) return null;

int mid = start + (end - start)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,start,mid - 1);
root.right = helper(nums,mid + 1 ,end);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0) return null;
return helper(nums,0,nums.length-1);
}

Convert Sorted List to Binary Search Tree

将有序链表转化为平衡二叉树

这道题思路实在是太骚气了

我们换一个思路可能就会简单很多,即如果是将一个排序二叉树转换成链表,无非是一个中序遍历。

那么,这里讲链表转换成二叉树也是一样的思路,即一个中序遍历,其具体思路如下。

按照中序遍历的思路,应该先生成左子树,然后是根节点,最后的右子树。以这样的顺序,每次新创建的节点都对应链表的顺序遍历中当前位置的节点。

很明显这是一个递归的结构。那么剩下的问题就是如何确定递归的终止条件。

因为在转换的过程中,需要计算各子链表的长度,那么这里就可以由此来终止递归,即当长度等于0时终止。下面我们来看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private int getLength(ListNode head){
int length = 0;
while (null != head){
head = head.next;
++length;
}
return length;
}
ListNode curr;
public TreeNode sortedListToBST(ListNode head) {
int size = getLength(head);
curr = head;
return helper(size);
}
public TreeNode helper(int size){
if(size == 0) return null;
TreeNode left = helper(size / 2);
TreeNode root = new TreeNode(curr.val);
curr = curr.next;
root.left = left;
root.right = helper(size - size / 2 - 1);
return root;
}

Delete Node in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public TreeNode deleteNode(TreeNode root, int key) {
if(null == root){
return null;
}
TreeNode dummy = new TreeNode(0);
if(root.val < 0){dummy.left = root;
}else{dummy.right = root;}
TreeNode parent = dummy;
TreeNode child = root;
while (null != child){
if(child.val == key){
break;
}else if(child.val < key){
parent = child;
child = child.right;
}else {
parent = child;
child = child.left;
}
}
if(null == child){
return root;
}
if(null == child.left){
if(child.val < parent.val){
parent.left = child.right;
}else {
parent.right = child.right;
}
}else if(null == child.right){
if(child.val < parent.val){
parent.left = child.left;
}else {
parent.right = child.left;
}
}else{ // 都不为空
// 找到该节点的右子树中的最左孩子
TreeNode afterParent = child;
TreeNode after = child.right;
while (null != after.left){
afterParent = after;
after = after.left;
}
// 把它的值与删除的节点的值进行交换
int temp = after.val;
after.val = child.val;
child.val = temp;
// 删除这个节点
if(temp < afterParent.val){
afterParent.left = after.right;
}else{
afterParent.right = after.right;
}
}
if(null != dummy.left){
return dummy.left;
}else{
return dummy.right;
}
}

还有一种递归写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;

if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;

TreeNode rightSmallest = root.right;
while (rightSmallest.left != null) rightSmallest = rightSmallest.left;
rightSmallest.left = root.left;
return root.right;
}
return root;
}

Find Mode in Binary Search Tree

给一个有重的BST。其中左子树小于等于本身,右子树大于本身。统计最多次数出现的数字。

思路:中序遍历计数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int maxCount;
List<Integer> set;

public int[] findMode(TreeNode root) {
maxCount = 0;
set = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
int preVal = Integer.MAX_VALUE;
int preCount = 0;
while (!stack.isEmpty() || null != root){
while (null != root){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(root.val == preVal){
++preCount;
}else {
preVal = root.val;
preCount = 1;
}
if(preCount > maxCount){
set.clear();
set.add(preVal);
maxCount = preCount;
}else if(preCount == maxCount){
set.add(preVal);
}
root = root.right;
}

int[] res = new int[set.size()];
int i = 0;
for(int e : set){
res[i] = e;
++i;
}
return res;
}

Serialize and Deserialize BST

实现BST的序列化和反序列化。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
sb.append(root.val);
sb.append(",");
if(root.left != null) sb.append(serialize(root.left));
if(root.right != null) sb.append(serialize(root.right));
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] str = data.split(",");
if(str.length == 0) return null;
if(str[0].length() == 0) return null;
Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(Integer.valueOf(str[0]));
stack.push(root);
for(int i = 1; i < str.length; ++i){
TreeNode curr = new TreeNode(Integer.valueOf(str[i]));
// 为当前的curr节点寻找插入位置
TreeNode out = null;
// 将所有比curr小的节点全pop出去
//(除了最后一个pop出去的节点外,
// 这些比curr小的节点都不可能有左右子树了)
while (!stack.isEmpty() && curr.val > stack.peek().val){
out = stack.pop();
}
// 如果curr大于最后一个pop出去的节点,那curr一定是最后一个pop出去的右节点
if(out != null && curr.val > out.val){
out.right = curr;
}else{
// 否则,那它就是栈顶的左节点
stack.peek().left = curr;
}
stack.push(curr);
}
return root;
}

还有很多相关题。

完全二叉树

Count Complete Tree Nodes

求完全二叉树的节点个数。

一开始就暴力数,当然是超时了。

下面是一种参考网上的巧妙的解法。主要是二分 + 位操作 \(2^n = n << 1\)

完全二叉树的一个性质是,如果左子树最左边的深度,等于右子树最右边的深度,说明这个二叉树是满的,即最后一层也是满的,则以该节点为根的树其节点一共有2^h-1个。如果不等于,则是左子树的节点数,加上右子树的节点数,加上自身这一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private int LeftLevel(TreeNode node){
if(node == null) return 0;
return 1 + LeftLevel(node.left);
}
private int rightLevel(TreeNode node){
if(node == null) return 0;
return 1 + rightLevel(node.right);
}
private int helper(TreeNode node){
if(node == null) return 0;
int leftLevel = LeftLevel(node.left) + 1;
int rightLevel = rightLevel(node.right) + 1;
if(leftLevel == rightLevel){ // 满二叉树节点个数 = 2^n - 1
//System.out.println(node.val + "\t" + leftLevel + "\t" + ((leftLevel << 1) - 1));
return (1 << leftLevel) - 1;
}
int nodeNums = helper(node.left) + helper(node.right) + 1;
//System.out.println(node.val + "\t" + leftLevel + "\t" + nodeNums);
return nodeNums;
}
public int countNodes(TreeNode root) {
return helper(root);
}

在这其中是存在重复计算的。同一个节点的数高度可能被计算多次。下面这种解法巧妙地避开了重复计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int countNodes(TreeNode root) {
return countNodes(root, -1, -1);
}

private int countNodes(TreeNode root, int lheight, int rheight){
// 如果没有上轮计算好的左子树深度,计算其深度
if(lheight == -1){
lheight = 0;
TreeNode curr = root;
while(curr != null){
lheight++;
curr = curr.left;
}
}
// 如果没有上轮计算好的右子树深度,计算其深度
if(rheight == -1){
rheight = 0;
TreeNode curr = root;
while(curr != null){
rheight++;
curr = curr.right;
}
}
// 如果两个深度一样,返回2^h-1
if(lheight == rheight) return (1 << lheight) - 1;
// 否则返回左子树右子树节点和加1
return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);
}

骚操作

还有一种操作:

用迭代法的思路稍微有点不同,因为不再是递归中那样的分治法,我们迭代只有一条正确的前进方向。所以,我们判断的时左节点的最【左】边的深度,和右节点的最【左】边深度。因为最后一层结束的地方肯定在靠左的那侧,所以我们要找的就是这个结束点。如果两个深度相同,说明左子树和右子树都是满,结束点在右侧,如果右子树算出的最左深度要小一点,说明结束点在左边,右边已经是残缺的了。根据这个大小关系,我们可以确定每一层的走向,最后找到结束点。另外,还要累加每一层的节点数,最后如果找到结束点,如果结束点是左节点,就多加1个,如果结束点是右节点,就多加2个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int countNodes(TreeNode root) {
int count = 0;
int h = minHeight(root);
while (root != null) {
int leftH = h - 1;
int rightH = minHeight(root.right);
if (rightH == leftH) { // 是满二叉树
count += 1 + getCount(leftH);
root = root.right;
h = rightH;
} else { //肯定是左边残缺
count += 1 + getCount(rightH);
root = root.left;
h = leftH;
}
}
return count;
}

private int minHeight(TreeNode root) {
int h = 0;
while (root != null) {
root = root.left;
h++;
}
return h;
}

private int getCount(int h) {
return (1 << h) - 1;
}

参考文献

  1. 刷题】二叉树非递归遍历
  2. 二叉树前序,中序,后序遍历迭代实现详解
  3. 【算法导论】二叉搜索树的插入和删除