从上到下打印二叉树Ⅱ
剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（Leetcode）
题目要求
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
提示：
节点总数 <= 1000
思路分析
代码实现
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
|
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i=0;i<k;i++){
TreeNode t = queue.poll();
temp.add(t.val);
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(temp);
}
return res;
}
}
|
从上到下打印二叉树Ⅲ
剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（Leetcode）
题目要求
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[20,9],
[15,7]
]
|
提示
节点总数 <= 1000
思路分析
- 根据题意分析，奇数行从左向右打印，偶数行从右向左打印；
- 基本思路可以参考上一题；
- 我们只需要定义一个变量sum，初始为1，while循环最后sum++，然后在执行时进行判断，如果时奇数就不变，如果是偶数就从集合的前面插入元素(默认集合都是在后面插入元素)。
- 因为使用addFirst方法，临时集合需要改用为链表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
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
|
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
int sum = 1;
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
LinkedList<Integer> temp = new LinkedList<>();
for(int i=0;i<k;i++){
TreeNode t = queue.poll();
if(sum % 2 == 1){
temp.add(t.val);
}else{
temp.addFirst(t.val);
}
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(temp);
sum++;
}
return res;
}
}
|
二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣（Leetcode）
题目要求
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
例子：
1
2
3
4
5
| 输入: [1,6,3,2,5]
输出: false
输入: [1,3,2,6,5]
输出: true
|
提示：
数组长度 <= 1000
思路分析
递归
后序遍历，根节点都是在末尾，通过二叉搜索树的特性(左子树所有节点小于根节点，右子树所有节点大于根节点)，可以分割左右子树，然后左右子树的头节点也是在末尾，可以根据特性将子树再进行分割。
单调栈（参考Leetcode题解-数据结构和算法）
他的后续遍历结果是：
[3,6,5,9,8,11,13,12,10]
从前往后不好看，我们来从后往前看：
[10,12,13,11,8,9,5,6,3]
发现两个规律：
遍历数组的所有元素，如果栈为空，就把当前元素压栈。如果栈不为空，并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点。
代码实现
递归
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
| class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null){
return true;
}
return f(postorder,0,postorder.length-1);
}
boolean f(int[] postorder,int i,int j){
if(i>=j){
return true;
}
int root = postorder[j];
int p = i;
while(postorder[p] < root) p++;
for(int k=p;k<j;k++){
if(postorder[k] < root){
return false;
}
}
return f(postorder,i,p-1) && f(postorder,p,j-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
| class Solution {
public boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int parent = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i >= 0; i--) {
int cur = postorder[i];
while (!stack.isEmpty() && stack.peek() > cur){
parent = stack.pop();
}
if (cur > parent)
return false;
stack.add(cur);
}
return true;
}
}
|
二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（Leetcode）
题目要求
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
例子1：
1
2
| 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
|
例子2：
1
2
| 输入：root = [1,2,3], targetSum = 5
输出：[]
|
提示：
- 树中节点总数在范围
[0, 5000] 内
-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
思路分析
- 根据题意，要求找出左子树节点之和以及右子树节点之和都等于target的路径；
- 使用深度优先搜索来解决该题：
- 从根节点开始，查找左子树，每经过一个节点(包括根节点)，将让target减去该节点，直到最后一个节点，如果target减去最后一个节点不为0，说明该路径不符合，就回溯查找上一个节点的右子树，直到target减去最后一个节点后结果为0，说明该路径符合要求；
- 然后从根节点开始，查找右子树，先寻找右子树，直到target减去最后一个节点，若不为0，就回溯到上一个节点的左子树进行查找，直到target减去节点结果为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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public List<List<Integer>> pathSum(TreeNode root, int target) {
res = new ArrayList<>();
temp = new ArrayList<>();
dfs(root,target);
return res;
}
void dfs(TreeNode root,int target){
if(root == null){
return;
}
temp.add(root.val);
target = target - root.val;
if(root.left == null && root.right == null && target == 0){
res.add(new ArrayList<>(temp));
}
dfs(root.left,target);
dfs(root.right,target);
temp.remove(temp.size()-1);
}
}
|
复杂链表的复制
剑指 Offer 35. 复杂链表的复制 - 力扣（Leetcode）
题目要求
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
例子1：
1
2
| 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
|
例子2：
1
2
| 输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
|
例子3：
1
2
3
| 输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
|
提示：
-10000 <= Node.val <= 10000Node.random 为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
思路分析
复制+拆分
例如：有A->B->C->D四个节点，再random下为：A->C,C->A,B->D,D->B；
- 将每个节点复制一份，即：A->A’->B->B’->C->C’->D->D’，并且有一个cur指针指向第一个A；
- 让cur.next.random = cur.random.next;（例如：A(cur.next.random) = A’->C’）
- 复制过后不能改变原来链表指针的状态；
- 拆分：例如：把A->A’->B->B’->C->C’ 拆分为：A->B->C和A’->B’->C’；
代码实现
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
|
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
while(cur != null){
Node curNew = cur.next;
curNew.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
Node headNew = head.next;
cur = head;
Node curNew = head.next;
while(cur != null){
cur.next = cur.next.next;
cur = cur.next;
curNew.next = cur == null ? null : cur.next;
curNew = curNew.next;
}
return headNew;
}
}
|
