# 某研究院的二叉树深度优先遍历变种的算法面试题以及答案

3，6，5
3，7，4

package cn.outofmemory;

import java.util.Stack;

public class TreeSum {
public static void main(String[] args) {
int expectSum = 22;

// declare tree
TreeNode root = new TreeNode(12, new TreeNode(6, new TreeNode(4),
new TreeNode(7)), new TreeNode(3, new TreeNode(2),
new TreeNode(7)));

Stack<StackData> stack = new Stack<StackData>();

while (!stack.isEmpty()) {
StackData top = stack.peek();
TreeNode temp = top.value;

//如果栈顶元素是叶子节点，计算看是否满足条件
if (temp.isLeaf()) {
int sumOfStack = getSumOfStack(stack);
if(sumOfStack == expectSum) {
printStack(stack);
}

//弹出叶子节点
stack.pop();

if(top.nodeType == NodeType.left) {
temp = stack.peek().value;
//如果有右子树，将右子树放入栈顶；如果没有，则循环弹出，直到有右子树的情况
if(temp.getRightNode() == null) {
while(temp.getRightNode() == null){
StackData popAgain = stack.peek();
if (popAgain.value.getRightNode() == null) {
popAgain = stack.pop();
temp = popAgain.value;
}
}
} else {
stack.push(new StackData(temp.getRightNode(),NodeType.right));
}
continue;
} else if (top.nodeType == NodeType.right) {
//如果叶子节点是右子节点，那么还要再次弹出
StackData popAgain = stack.pop();
while (popAgain.nodeType == NodeType.right) {
popAgain = stack.pop();
}
if(!stack.isEmpty()) {
StackData nowTop = stack.peek();
if(nowTop.value.getRightNode() != null) {
stack.push(new StackData(nowTop.value.getRightNode(),NodeType.right));
}
}
} else {
//如果是根节点说明遍历完了，要将根节点弹出并结束循环
stack.pop();
continue;
}

} else {
//将所有的左子节点压栈
while (temp.getLeftNode() != null) {
temp = temp.getLeftNode();
}
}
}

}

private static void printStack(Stack<StackData> stack) {
for (StackData sd : stack) {
System.out.print("" + sd.value.getValue() + " ");
}
System.out.println();
}

private static int getSumOfStack(Stack<StackData> stack) {
int result = 0;
for (StackData sd : stack) {
result += sd.value.getValue();
}
return result;
}

package cn.outofmemory;

public class TreeNode {

public TreeNode() {

}

public TreeNode(int value) {
this.value = value;
}

public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.setLeftNode(left);
this.setRightNode(right);
}

private TreeNode left;
private TreeNode right;
private int value;

protected void setLeftNode(TreeNode left) {
this.left = left;
}

public TreeNode getLeftNode() {
return this.left;
}

protected void setRightNode(TreeNode right) {
this.right = right;
}

public TreeNode getRightNode() {
return this.right;
}

public int getValue() {
return this.value;
}

public boolean isLeaf() {
return this.left == null && this.right == null;
}

NodeType枚举的定义如下：

package cn.outofmemory;

public enum NodeType {
root,left,right;
}

StackData类定义如下，该类对TreeNode节点进行了封装，对于每个压栈的数据都添加了NodeType的属性，通过这个NodeType可以知道当前节点的类型。

package cn.outofmemory;

public class StackData {
public TreeNode value;
public NodeType nodeType;

public StackData(TreeNode value, NodeType type) {
this.value = value;
this.nodeType = type;
}
}

http://outofmemory.cn/code-snippet/4247/binary-tree-deep-first-enum-test

|
24天前
|

“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
18 1
|
27天前
|

Java面试题：解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题：解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
28 1
|
1月前
|

19 3
|
1月前
|

JS 【详解】树的遍历（含深度优先遍历和广度优先遍历的算法实现）
JS 【详解】树的遍历（含深度优先遍历和广度优先遍历的算法实现）
21 0
|
27天前
|

Java面试题：解释Java的垃圾回收机制，包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题：解释Java的垃圾回收机制，包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
23 0
|
27天前
|

Java面试题：Java内存探秘与多线程并发实战，Java内存模型及分区：理解Java堆、栈、方法区等内存区域的作用，垃圾收集机制：掌握常见的垃圾收集算法及其优缺点
Java面试题：Java内存探秘与多线程并发实战，Java内存模型及分区：理解Java堆、栈、方法区等内存区域的作用，垃圾收集机制：掌握常见的垃圾收集算法及其优缺点
21 0
|
27天前
|

Java面试题：解释JVM的内存结构，并描述堆、栈、方法区在内存结构中的角色和作用，Java中的多线程是如何实现的，Java垃圾回收机制的基本原理，并讨论常见的垃圾回收算法
Java面试题：解释JVM的内存结构，并描述堆、栈、方法区在内存结构中的角色和作用，Java中的多线程是如何实现的，Java垃圾回收机制的基本原理，并讨论常见的垃圾回收算法
18 0
|
1月前
|

JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
23 0
|
20天前
|

MCKP-MMF算法是一种启发式流量估计方法，用于寻找无线传感器网络的局部最优解。它从最小配置开始，逐步优化部分解，调整访问点的状态。算法处理访问点的动态影响半径，根据带宽需求调整，以避免拥塞。在MATLAB 2022a中进行了仿真，显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段：慢启动阶段识别瓶颈并重设半径，随后进入周期性调整阶段，追求最大最小公平性。
30 1
|
4天前
|

17 4