写点什么

如何在没有递归的情况下通过对给定二叉树执行中序遍历来打印所有节点?

作者:InfoQ IT百科
  • 2022 年 4 月 24 日
  • 本文字数:394 字

    阅读完需:约 1 分钟

解题思路:既然要求不能使用递归,我们可以用一个栈的数据结构,来模拟递归实现时的函数调用。通过循环和栈数据结构来实现中序遍历。


解题思路:既然要求不能使用递归,我们可以用一个栈的数据结构,来模拟递归实现时的函数调用。通过循环和栈数据结构来实现中序遍历。


实现代码如下:

public static void inorderTraversal(Node root) {        if(root == null) {            return;        }
Stack<Node> stack = new Stack<>(); Node cur = root;
while(true) { while(cur != null) { stack.push(cur); cur = cur.left; }
if(stack.empty()) { break; } Node top = stack.pop(); // 打印当前节点值 System.out.print(top.val + " "); cur = top.right; } }
复制代码


用户头像

还未添加个人签名 2021.04.12 加入

还未添加个人简介

评论

发布
暂无评论
如何在没有递归的情况下通过对给定二叉树执行中序遍历来打印所有节点?_InfoQ IT百科_InfoQ写作社区