概述
1. 从上打下打印二叉树
（1）题目描述
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回：
[3,9,20,15,7]
（2）题目分析
本题可以通过队列来求解，通过依次将每个结点的左右子节点入队，然后出队，即可实现从上到下打印二叉树。
（3）代码
package swordOffer.day8;
import leetcode.week2.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @author chengzhengda
* @version 1.0
* @date 2020-04-07 11:28
* @desc
*/
public class t36 {
public static int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
LinkedList<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
arrayList.add(temp.data);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
int[] res = new int[arrayList.size()];
for (int i = 0; i < arrayList.size(); i++) {
res[i] = arrayList.get(i);
}
return res;
}
public static void main(String[] args) {
TreeNode node11 = new TreeNode(4);
TreeNode node12 = new TreeNode(1);
TreeNode node13 = new TreeNode(1);
TreeNode node14 = new TreeNode(2);
TreeNode node15 = new TreeNode(3);
TreeNode node16 = new TreeNode(3);
TreeNode node17 = new TreeNode(2);
node11.left = node12;
node11.right = node13;
node12.left = node14;
node12.right = node15;
node13.left = node16;
node13.right = node17;
int res[] = levelOrder(node11);
for (int i : res) {
System.out.println(i);
}
}
}
2. 从上到下打印二叉树 II
（1）题目描述
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
（2）题目分析
本题可以在第一题的基础上进行优化，通过设置2个变量，last和nlast，last表示上一行的最后一个结点，nlast表示当前节点的最右子节点。当当前结点等于last时，说明当前节点到达了当前行的最后一个节点，则nlast即为下一行的最后一个结点，然后更新last为nlast。
（3）代码
package swordOffer.day8;
import leetcode.week2.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @author chengzhengda
* @version 1.0
* @date 2020-04-07 22:40
* @desc
*/
public class t37 {
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
LinkedList<TreeNode> queue = new LinkedList<>();
List<List<Integer>> arrayList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
TreeNode last = root;
TreeNode nlast = null;
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
list.add(temp.data);
if (temp.left != null) {
nlast = temp.left;
queue.offer(temp.left);
}
if (temp.right != null) {
nlast = temp.right;
queue.offer(temp.right);
}
if (last == temp && !queue.isEmpty()) {
last = nlast;
arrayList.add(list);
list = new ArrayList<>();
}
}
arrayList.add(list);
return arrayList;
}
public static void main(String[] args) {
TreeNode node11 = new TreeNode(4);
TreeNode node12 = new TreeNode(1);
TreeNode node13 = new TreeNode(1);
TreeNode node14 = new TreeNode(2);
TreeNode node15 = new TreeNode(3);
TreeNode node16 = new TreeNode(3);
TreeNode node17 = new TreeNode(2);
node11.left = node12;
node11.right = node13;
node12.left = node14;
node12.right = node15;
node13.left = node16;
node13.right = node17;
List<List<Integer>> lists = levelOrder(node11);
for (List<Integer> list : lists) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
3. zigzag打印二叉树
（1）题目描述
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
（2）题目分析
本题需要对奇偶数行分开处理，对于奇数行，从左到右进行入队和出队，对于偶数行，从右到左进行入队和出队。
（3）代码
package swordOffer.day8;
import leetcode.week2.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @author chengzhengda
* @version 1.0
* @date 2020-04-07 23:25
* @desc
*/
public class t38 {
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
LinkedList<TreeNode> queue = new LinkedList<>();
List<List<Integer>> arrayList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
TreeNode last = root;
TreeNode nLast = null;
boolean lr = true;
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = null;
if (lr) {
temp = queue.pollFirst();
list.add(temp.data);
if (temp.left != null) {
nLast = nLast == null ? temp.left : nLast;
queue.offerLast(temp.left);
}
if (temp.right != null) {
nLast = nLast == null ? temp.right : nLast;
queue.offerLast(temp.right);
}
} else {
temp = queue.pollLast();
list.add(temp.data);
if (temp.right != null) {
nLast = nLast == null ? temp.right : nLast;
queue.offerFirst(temp.right);
}
if (temp.left != null) {
nLast = nLast == null ? temp.left : nLast;
queue.offerFirst(temp.left);
}
}
if (last == temp && !queue.isEmpty()) {
lr = !lr;
last = nLast;
nLast = null;
arrayList.add(list);
list = new ArrayList<>();
}
}
arrayList.add(list);
return arrayList;
}
public static void main(String[] args) {
TreeNode node11 = new TreeNode(4);
TreeNode node12 = new TreeNode(1);
TreeNode node13 = new TreeNode(5);
TreeNode node14 = new TreeNode(2);
TreeNode node15 = new TreeNode(3);
TreeNode node16 = new TreeNode(3);
TreeNode node17 = new TreeNode(2);
node11.left = node12;
node11.right = node13;
node12.left = node14;
node12.right = node15;
node13.left = node16;
node13.right = node17;
List<List<Integer>> lists = levelOrder(node11);
for (List<Integer> list : lists) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
4. 二叉搜索树的后序遍历序列
（1）题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/
2 6
/
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
（2）题目分析
已知二叉树的后序遍历顺序为left->right->root，则二叉树的后序遍历的逆序为root->right->left，根据二叉树搜索的性质，可知逆序的前半部分为递增，后半部分为递减，因此，当逆序出现递减时，则前一个数肯定为当前的根节点。而左半部分肯定小于这个根节点。
（3）代码
package swordOffer.day8;
import java.util.Stack;
/**
* @author chengzhengda
* @version 1.0
* @date 2020-04-08 15:15
* @desc
*/
public class t39 {
public static boolean verifyPostorder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i >= 0; i--) {
if (postorder[i] > root) {
return false;
}
while (!stack.isEmpty() && stack.peek() > postorder[i]) {
root = stack.pop();
}
stack.add(postorder[i]);
}
return true;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 7, 6, 4};
System.out.println(verifyPostorder(arr));
}
}
5. 二叉树中和为某一值的路径
（1）题目描述
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
（2）题目分析
本题通过递归回溯法求解。
（3）代码
package swordOffer.day8;
import leetcode.week2.TreeNode;
import java.util.LinkedList;
import java.util.List;
/**
* @author chengzhengda
* @version 1.0
* @date 2020-04-08 16:54
* @desc
*/
public class t40 {
private List<List<Integer>> res = new LinkedList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
public void recur(TreeNode root, int tar) {
if (root == null) {
return;
}
path.add(root.data);
tar -= root.data;
if (tar == 0 && root.left == null && root.right == null) {
res.add(new LinkedList<>(path));
}
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
public static void main(String[] args) {
TreeNode node11 = new TreeNode(4);
TreeNode node12 = new TreeNode(1);
TreeNode node13 = new TreeNode(5);
TreeNode node14 = new TreeNode(7);
TreeNode node15 = new TreeNode(3);
TreeNode node16 = new TreeNode(3);
TreeNode node17 = new TreeNode(2);
node11.left = node12;
node11.right = node13;
node12.left = node14;
node12.right = node15;
node13.left = node16;
node13.right = node17;
t40 tt = new t40();
List<List<Integer>> res = tt.pathSum(node11, 12);
for (List<Integer> list : res) {
for (int i : list) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
最后
以上就是标致月饼为你收集整理的《剑指offer第二版》 八的全部内容，希望文章能够帮你解决《剑指offer第二版》 八所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复