IT 面试题库

用递归和非递归(显式栈)分别实现二叉树的前序、中序、后序遍历,并说明非递归写法中节点入栈/出栈的时机。

中级编程题算法工程师Java后端工程师二叉树遍历递归非递归栈

题目

考察点:递归与迭代两种思维、显式栈模拟调用栈、三种遍历在非递归下的差异(尤其后序的经典写法)。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 70 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

参考实现(中序非递归):

function inorder(root) {
  const res = [], stack = [];
  while (root || stack.length) {
    while (root) { stack.push(root); root = root.left; }   // 一路向左
    root = stack.pop();
    res.push(root.val);                                    // 出栈即访问
    root = root.right;                                     // 转向右子树
  }
  return res;
}

复杂度:时间 O(n),空间 O(h)(h 为树高,链表退化时 O(n))。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题