剑指offer刷题总结——树篇(三)
星级:1
1.按之字形顺序打印二叉树
【题目】
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
【代码】
package swear2offer.tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class T {
/** * 请实现一个函数按照之字形打印二叉树,即 * 第一行按照从左到右的顺序打印, * 第二层按照从右至左的顺序打印, * 第三行按照从左到右的顺序打印,其他行以此类推。 * */
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
if (pRoot == null) return new ArrayList<>();
int i,index,size;
TreeNode temp;
Queue<TreeNode> q = new LinkedList<>();
ArrayList<Integer> path = new ArrayList<>();
ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
q.add(pRoot);
path.add(pRoot.val);
paths.add(path);
index = 2;
size = 0;
while (!q.isEmpty()) {
size = q.size();
path = new ArrayList<>();
// 通过size+循环的方式,省去复杂的判断
for (i=0; i<size; i++) {
temp = q.remove();
if (temp.left != null) {
if (index % 2 == 0) {
path.add(0,temp.left.val);
} else {
path.add(temp.left.val);
}
q.add(temp.left);
}
if (temp.right != null) {
if (index % 2 == 0) {
path.add(0,temp.right.val);
} else {
path.add(temp.right.val);
}
q.add(temp.right);
}
}
paths.add(path);
index++;
}
paths.remove(paths.size()-1);
return paths;
}
}
【思考】
通过判断每一行多少个节点来遍历每一行
2.二叉搜索树的第 k 个结点
【题目】
给定一棵二叉搜索树,请找出其中的第 k 小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为 4。
【代码】
package swear2offer.tree;
import java.util.ArrayList;
public class Kth {
/** * 给定一棵二叉搜索树,请找出其中的第 k 小的结点。 * 例如,(5,3,7,2,4,6,8)中,按结点数值大小顺序第三小结点的值为 4。 * * 思路: * 先利用:左根右的中序遍历方式,获得排序数组,在输出第k位 * 优化:每次获得节点都计数,当存入第k个节点的时候,输出即可 * * 边界:k<1或者k大于树节点树 * */
ArrayList<TreeNode> res;
TreeNode KthNode (TreeNode pRoot, int k) {
if (pRoot == null || k < 1) return null;
res = new ArrayList<>();
find(pRoot,k);
if (res.size() < k) return null;
return res.get(k-1);
}
public void find (TreeNode pRoot, int k) {
if (pRoot!=null) {
find(pRoot.left,k);
res.add(pRoot);
if (res.size() >= k) return;
find(pRoot.right,k);
}
}
}
【思考】
- 思路: 先利用:左根右的中序遍历方式,获得排序数组,在输出第k位
- 优化:每次获得节点都计数,当存入第k个节点的时候,输出即可
- 边界:k<1或者k大于树节点树
- 注意,无论任何排序,先中后序,操作都是对根节点,左右子树只是递归
还没有评论,来说两句吧...