Heim > Fragen und Antworten > Hauptteil
比如,对于下面这个二叉树,它所有的路径为:
8 -> 3 -> 1
8 -> 2 -> 6 -> 4
8 -> 3 -> 6 -> 7
8 -> 10 -> 14 -> 13
怎么用Java去实现?
阿神2017-04-18 10:53:58
不用递归的话,那就深度优先啦!
采用栈, 首先将根结点压入栈,如果栈不为空,而后出栈并输出当前结点中值,而后先把右子树压入栈,再把左子树压入栈,再判断栈是否为空,循环.....
步骤如下:
1) 先把二叉树的根结点入栈
2)判断栈是否为空,不为空,则出栈,并输出出栈树结点的值
3)出栈树结点的右子树入栈
4)出栈树结点的左子树入栈
5)循环回到(2)
这是我之前看到的一个方法,不知道能不能帮到题主?
public void depthOrderTraversal(){
if(root==null){
System.out.println("empty tree");
return;
}
ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
stack.push(root);
while(stack.isEmpty()==false){
TreeNode node=stack.pop();
System.out.print(node.value+" ");
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
System.out.print("\n");
}