IT 面试题库

翻转一棵二叉树(左右子树互换),给出递归实现,并思考能否用层序遍历(非递归)完成?

高级编程题算法工程师Java后端工程师二叉树翻转递归镜像层序

题目

考察点:递归自顶向下翻转、非递归(层序)翻转、边界与『镜像』概念的延伸。这是二叉树操作类的经典追问。

参考答案

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

要点:

参考实现(递归):

function invertTree(root) {
  if (!root) return null;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

复杂度:O(n) 时间,递归 O(h) 空间。

练这道题

同分类 · 高频题

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

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