Boom LeetCode入门(五)二叉树

二叉树的前、中、后序遍历

二叉树经典问题之一,有关前中后序的遍历,主要通过递归和利用栈两种方式来实现,其中递归实现比较简单,思路如下↓

二叉树的前序遍历

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root != null){
//前序遍历
res.add(root.val);
postorderTraversal(root.left);
//中序遍历
//res.add(root.val);
postorderTraversal(root.right);
//后序遍历
//res.add(root.val);
}
return res;
}
}

借助栈实现三种遍历时,每种遍历下如何出栈入栈又有所区别,分别展开来讲

前序遍历

二叉树的前序遍历

前序遍历下,先让根节点入栈

之后逐步出栈,并判断出栈节点左右孩子是否为空,不为空则入栈

需要注意的是,由于栈的先入后出特性,右孩子先入栈,左孩子后入栈,每次出栈时打印节点信息,最终输出为先序遍历结果

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
res.add(temp.val);
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return res;
}
}

后序遍历

二叉树的后序遍历

后序遍历需要借助两个栈,stack1 stack2

头结点先入栈stack1,出栈时不直接打印,而是入栈stack2,同时比对当前节点左右孩子,此时左孩子先入栈,右孩子后入栈。这样stack1中弹出顺序,即stack2中的入栈顺序为头节点→右节点→左节点

所以最终stack2中出栈打印时为左节点→右节点→头节点,即为后序遍历顺序

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while(!stack1.isEmpty()){
TreeNode temp = stack1.pop();
stack2.push(temp);
if(temp.left != null){
stack1.push(temp.left);
}
if(temp.right != null){
stack1.push(temp.right);
}
}
while(!stack2.isEmpty()){
res.add(stack2.pop().val);
}
return res;
}
}

中序遍历

二叉树的中序遍历

中序遍历下,所有左边界先入栈,然后逐个出栈并检查出栈节点是否存在右子节点,存在的话将右子节点,以及其所有的左子边界节点全部出栈

何为左子边界?如↓

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode temp = stack.pop();
res.add(temp.val);
if(temp.right != null){
cur = temp.right;
}
}
return res;
}
}

二叉树的广度优先遍历

二叉树的层序遍历

二叉树的前序遍历即为深度优先遍历,在广度上的遍历则称之为广度优先遍历(层序遍历)

广度优先遍历利用队列FIFO的特性实现,最开始根节点入队列,然后开始出队列,每次出队时记录当前值,并比对当前出队节点的左右子节点是否为空,不为空则入队

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> resTemp = new ArrayList<>();
for(int i = queue.size(); i>0; i--){
TreeNode temp = queue.poll();
resTemp.add(temp.val);
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
res.add(resTemp);
}
return res;
}
}

由于出队时就能得到当前层的节点树,对上述算法稍加改进就能够得到树的最大宽度

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxlevel(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
max = queue.size() > max ? queue.size() : max;
for(int i = queue.size(); i>0; i--){
TreeNode temp = queue.poll();
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
return max;
}
}

特殊二叉树的判断

搜索二叉树

搜索二叉树结构如下↓

对于搜索二叉树中的每一个节点,其左子树的值都比它小,右子树的值都比它大

因此其左→头→右的中序遍历结果必定为一个有序的升序序列

验证二叉搜索树

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
long preVal = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
boolean isValid = isValidBST(root.left);
if(!isValid){
return false;
}
if(root.val <= preVal){
return false;
}
preVal = root.val;
return isValidBST(root.right);
}
}

完全二叉树

完全二叉树下节点的编号完全对应其在满二叉树下的编号(满二叉树定义如下:对于二叉树中的任一节点,除了叶子节点外,其它任意节点应当都是有左右孩子节点的。同时,满二叉树也是一种特殊的完全二叉树)

如下图中左边二叉树为一颗完全二叉树,右边二叉树则不是

判断一棵树是否为完全二叉树,借助层序遍历实现,层序遍历过程中的两个特殊情形:

  • 如果存在节点有右孩子,且无左孩子,该二叉树不是完全二叉树
  • 当第一次遇到左右孩子不齐全的节点时,后续所有节点应当为叶子节点

二叉树的完全性检验

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isCompleteTree(TreeNode root) {
//flag标记是否已经出现左右孩子不全的节点
int flag = 0;
if(root == null ) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp.left == null){
if(temp.right != null){
return false;
}else{
flag = 1;
break;
}
}
if(temp.left != null){
if(temp.right == null){
queue.offer(temp.left);
flag = 1;
break;
}else{
queue.offer(temp.left);
queue.offer(temp.right);
}
}
}
if(flag == 1){
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp.left != null || temp.right != null){
return false;
}
}
}
return true;
}
}

满二叉树

满二叉树具有如下性质,其高度h和节点数n必定满足

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
package p5.binaryTree;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

public class FullBinaryTree {
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
}

public boolean isFullBinaryTree(TreeNode root){
if(root == null) return true;
int h = 0;
int n = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
h++;
for(int i = queue.size(); i>0; i--){
TreeNode temp = queue.poll();
n++;
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
}
}
return n == (Math.pow(2, h) - 1);
}
}

平衡二叉树

对于任何一个子树,其左子树和右子树的高度差都不超过一的二叉树为平衡二叉树

剑指 Offer 55 - II. 平衡二叉树

解决该问题的核心在于,对每一个节点需要进行三个判断:

  • 左子树是否为平衡二叉树
  • 右子树是否为平衡二叉树
  • 左右子树高度差是否不超过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
32
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class reType{
boolean bal;
int high;
reType(boolean bal, int high){
this.bal = bal;
this.high = high;
}
}
public boolean isBalanced(TreeNode root) {
return process(root).bal;
}
public reType process(TreeNode root){
if(root == null){
return new reType(true, 0);
}
reType rA = process(root.left);
reType rB = process(root.right);
reType res = new reType(rA.bal && rB.bal && (Math.abs(rA.high - rB.high) < 2),
Math.max(rA.high, rB.high) + 1);
return res;
}
}

该算法的解题思路,适用于所有的树形DP问题,吃透它!(例如:思考下如何通过树形DP实现搜索二叉树)

公共祖先节点

面试题 04.08. 首个共同祖先

公共节点存在如下两种情况:

  • node1为node2的祖先,或node2为node1祖先
  • node1和node2有其它公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q){
return root;
}
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
//左右子树均有返回值
if(l != null && r != null){
return root;
}
//左右子树并不都有返回值
return l == null ? r : l;
}
}

后继节点

后继节点,即中序遍历中,一个节点的下一个节点即为后继节点

由于此时的二叉树结构中给出了parent指针,那么就可以利用该特性来降低通过中序遍历来实现该代码的时间复杂度

对于该数据类型的二叉树,具有如下特性:

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
package p5.binaryTree;

//中序后继节点
public class MiddleNextNode {
class TreeNode{
TreeNode left;
TreeNode right;
TreeNode parent;
int val;
TreeNode(int val){
this.val = val;
}
}

public TreeNode minddleNextNode(TreeNode node){
if(node == null) return null;
if(node.right != null){
return getNearLeft(node.right);
}else{
TreeNode parent = node.parent;
while(parent != null && parent.left != null){
node = parent;
parent = node.parent;
}
return parent;
}

}

//返回右子树节点的第一个左叶子节点
private TreeNode getNearLeft(TreeNode node) {
if(node == null){
return null;
}
while(node.left != null){
node = node.left;
}
return node;
}
}

二叉树的序列化与反序列化

剑指 Offer II 048. 序列化与反序列化二叉树

序列化反序列化均可利用递归实现,以前序遍历为序列化反序列化依据实现↓

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null){
return "null,";
}
String res = root.val + ",";
res += serialize(root.left);
res += serialize(root.right);
return res;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null) return null;
String[] nodes = data.split(",");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < nodes.length; i++){
queue.offer(nodes[i]);
}
return process(queue);
}

public TreeNode process(Queue<String> queue){
String temp = queue.poll();
if(temp.equals("null")){
return null;
}
TreeNode tempNode = new TreeNode(Integer.valueOf(temp));
tempNode.left = process(queue);
tempNode.right = process(queue);
return tempNode;
}
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

折纸问题

折纸问题(微软面试题)

问题描述:

请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。此时 折痕是凹下去的,即折 痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次,压出折痕后展开,此时有三条折痕,从上 到下依次是下折痕、下折痕和上折痕。 给定一 个输入参数N,代表纸条都从下边向上方连续对折N次,请从上到下打印所有折痕的方向 例如:N=1时,打 印:凹;N=2时,打印: 凹 凹 凸

规律

通过折纸操作发现,最后打印的结果应该是一个左子树全部为凹右子树全部为凸的二叉树结构

最后通过中序遍历进行打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package p5.binaryTree;

public class Origami {
public static void main(String[] args) {
int N = 3;
//三个传入参数分别表示,当前为第几次折叠、一共折叠多少次、折痕为凹用true表示
origami(1, N, true);
}

private static void origami(int i, int n, boolean b) {
if(i > n){
return;
}
origami(i+1, n, true);
System.out.print(b ? "凹 " : "凸 ");
origami(i+1, n, false);
}
}

总结

二叉树的相关算法中,重点是掌握DFS和BFS的方法,并利用DFS和BFS完成特殊问题的求解。