本篇文章介绍二叉树中除了前序、中序、后续遍历以外的其他一些遍历方式。
首先，还是定义树的节点如下
public class TreeNode {
public Integer data;
public TreeNode leftChild;
public TreeNode rightChild;
}
按层遍历二叉树
考虑使用一个队列作为辅助容器，然后将根节点首先入队，接下来按下面三个步骤执行：
1、队列不为空，从队列头部取出一个节点，打印该节点。
2、如果该节点有左子节点，则将左子节点放入队尾，如果有右子节点，则将右子节点也放入队列队尾。
3、重复步骤1。
public List<TreeNode> deepOrder(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(cur);
while (!queue.isEmpty()) {
cur = queue.poll();
result.add(cur);
if (cur.leftChild != null) {
queue.add(cur.leftChild);
}
if (cur.rightChild != null) {
queue.add(cur.rightChild);
}
}
return result;
}
打印指定层的节点
方法一
我们上面已经实现了二叉树的按层遍历，如果我们在访问节点时能够知道当前节点处于哪一层，那么问题迎刃而解。
为了能够“知道”当前节点处的层次，可以考虑使用一个Map来保存每个节点的层次信息。
public List<TreeNode> visitSpecifiedLevel(int level) {
if (level <= 0 || root == null) {
return Collections.emptyList();
}
List<TreeNode> result = new ArrayList<>();
TreeNode cur = root;
// 存储节点层级的map
Map<TreeNode, Integer> levelMap = new HashMap<>();
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(cur);
// 根节点为第一层
levelMap.put(cur, 1);
while (!queue.isEmpty()) {
cur = queue.poll();
int curLevel = levelMap.get(cur);
if (curLevel == level) {
result.add(cur);
} else if (curLevel < level) {
if (cur.leftChild != null) {
queue.add(cur.leftChild);
levelMap.put(cur.leftChild, curLevel + 1);
}
if (cur.rightChild != null) {
queue.add(cur.rightChild);
levelMap.put(cur.rightChild, curLevel + 1);
}
} else {
break;
}
}
return result;
}
方法二
采用递归，不需要任何辅助容器：
public List<TreeNode> visitSpecifiedLevel2(int level) {
if (level <= 0 || root == null) {
return Collections.emptyList();
}
return subVisit(Collections.singletonList(root), level, 1);
}
public List<TreeNode> subVisit(List<TreeNode> parentNodes, int level, int curLevel) {
if (level == curLevel) {
return parentNodes;
}
List<TreeNode> result = new ArrayList<>();
for (TreeNode node: parentNodes) {
if (node.leftChild != null) {
result.add(node.leftChild);
}
if (node.rightChild != null) {
result.add(node.rightChild);
}
}
return subVisit(result, level, curLevel + 1);
}
获取二叉树的深度
所谓树的深度，就是从根节点到叶子节点的所有路径中，最长的那个路径的长度。
考虑一般情况，如果一棵树只有一个根节点，那么他的深度是1，如果根节点有左子树或右子树，那么树的深度应该是左子树或右子树深度较大的那个值再加上1。
利用递归，很容易实现上面的思路：
private int deep(TreeNode parent) {
int leftDeep = 0;
int rightDeep = 0;
if (parent.leftChild != null) {
leftDeep = deep(parent.leftChild);
}
if (parent.rightChild != null) {
rightDeep = deep(parent.rightChild);
}
return leftDeep > rightDeep ? rightDeep + 1 : leftDeep + 1;
}
路径求和
从根节点到某个叶子节点，途中经过的所有节点形成一条路径。如果给定一个值，我们如何找到节点之和等于该值的所有路径呢？
可以考虑先序遍历，具体分为下面几个步骤
1、采用先序遍历，并记录当前栈中元素之和。当到达叶子节点时，判断栈内元素之和是否与给定值相等。
2、如果相等，则打印栈中所有元素，不满足则执行第三步。
3、弹出栈顶元素，然后看其是否有右孩子，如果有，则执行第一步，如果没有则继续弹栈。
public static void print2(TreeNode root, int sum) {
Deque<TreeNode> stack = new ArrayDeque<>();
int curSum = 0;
subPrint2(root, sum, curSum, stack);
}
private static void subPrint2(TreeNode root, int sum, int curSum, Deque<TreeNode> stack) {
stack.push(root);
curSum += root.data;
boolean isLeaf = root.leftChild == null && root.rightChild == null;
// 叶子节点，并且路径之和与给定值相等
if (isLeaf && sum == curSum) {
Iterator<TreeNode> it = stack.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println("--- split line ---");
}
if (root.leftChild != null) {
subPrint2(root.leftChild, sum, curSum, stack);
}
if (root.rightChild != null) {
subPrint2(root.rightChild, sum, curSum, stack);
}
// 弹出栈顶元素，并减少curSum值
TreeNode poped = stack.pop();
curSum -= poped.data;
}
完！
网友评论