乐趣区

关于java:offer-27-二叉树的镜像

二叉树的镜像

定义

对于二叉树中任意节点 root,设其左 / 右子节点别离为 left, right;则在二叉树的镜像中的对应 root 节点,其左 / 右子节点别离为 right, left。

办法一:递归法

  • 依据二叉树镜像的定义,思考递归遍历(dfs)二叉树,替换每个节点的左 / 右子节点,即可生成二叉树的镜像。
  • 当节点为空的时候,就阐明曾经替换结束
  • 须要先定义一个辅助节点,用来暂存替换的节点


办法二:辅助栈(或队列)

利用栈(或队列)遍历树的所有节点 nodenode,并替换每个 nodenode 的左 / 右子节点。

  • 先把根节点入栈,而后出战,而后左右节点入栈,再出栈,先进后出
  • 这个栈看起来更直观

    还是用 linkedlist 更好,stack 都快被放弃了
退出移动版