js如何递归实现反转二叉树

前端 潘老师 3个月前 (11-27) 67 ℃ (0) 扫码查看

本文主要讲解关于js如何递归实现反转二叉树相关内容,让我们来一起学习下吧!

递归是一个很有意思的思考方式,关于递归的解释很简单:

递归(英语:Recursion),在数学和计算机科学中是指在函数的定义中使用函数自身的方法,在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

刚开始接触递归,看不懂也算常态吧。即使熟悉了,部分代码的递归流程也需要消化一下。这种调用自身的状况,就让人很迷惑,毕竟现实中不存在调用自身的可能。就好比高数考试中,遇到不会的,紧急问自己,这道题涉及的知识点是什么,快告诉我。大脑得到的结论,大概也只是你自己上课认真听讲没有,心里没数吗?

宽慰过后,来思考一下递归流程。代码中,递归需要两个条件,一是边界值,而是子过程拆解。

先看为什么需要边界值。递归的过程也就是函数入栈,无非这个函数是由自身调用的。如果没有边界返回,就会栈溢出。当栈顶部函数弹出后,下面的函数都会随之一一出栈。这就有一种在代码中穿行的感觉,进入一个函数,再进入下一个,一路穿行到最后一个函数的 return 语句,再原路返回。

在写递归代码的时候,确立边界条件,永远是第一步。不同的边界条件(例如树,是递归到叶节点,还是叶节点的左右两个空节点),可能会影响子过程处理,进而影响代码的简洁程度。思考递归,通常和数据结构相关。不明白的时候,直接定位到数据的幺元上思考怎么处理。

例如 Haskell 中的递归写法,常常能看到这样的 pattern match 写法,到达空的 list 就返回:

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =  
  let smallerSorted = quicksort [a | a <- xs, a <= x] 
      biggerSorted = quicksort [a | a <- xs, a > x]  
  in smallerSorted ++ [x] ++ biggerSorted

Haskell 没有循环控制语句,总说递归和循环是等价的,看过代码会更有感觉。

或者,把边界条件当作异常拦截思考也可以。这部分不是那么难,多写一写就会有感觉。

接下来是拆解子过程,这一部分才是容易把人绕晕的,我的经验告诉我,绕晕多半是因为想的太多。

举一个经典的例子,反转二叉树。

二叉树就是一个 Root 节点,下面有左右两个子树的结构,大概这个样子

root

/  \

left right

递归边界条件就像上面说的,叶节点或者空节点都可以,空节点显得更简洁。

子过程会让人绕晕的原因是,很多时候想在脑子里把整个过程走完。就像在你的脑子里跑变身的过程动画,哇这一层的左手臂拆下来安到了右边,右手臂安到了左边,随后父级也开始了变形!!!

人脑还是有极限的,这样去思考很容易过载。递归的重点就是要相信,Codes find a way。成熟的代码会自己找到结果,不需要有人指导它做每一步。

function mirrorTree(root) {
  // 递归第一步永远是确定递归边界条件
  if (!root) return root;
  // 递归调用
  // 只要边界条件对,就只需要思考,每一步究竟干了什么
  // 反转下一级
  // 至于其他的,递归会自己找到答案
  const left = mirrorTree(root.right);
  const right = mirrorTree(root.left);
  // 这里就是调换左右子树
  root.left = left;
  root.right = right;
  // 别忘了返回
  return root;
}

交换二叉树,就交换左右节点就行。同时左右子树也需要反转,那就去找下一级要。至于下一级怎么做,不管我的事,附庸的附庸,不是我的附庸。

当然,先反转当前层,再反转下一层也是可以的,但是思考上不如上一种递归,例如这样:

  // 先交换左右子树
  const temp = root.left
  root.left = root.right
  root.right = temp
  // 下一级起来干活
  mirrorTree(root.right);
  mirrorTree(root.left);

这种思考,方式也很直观,当前只需要交换左右子树,那就先交换。交换后发现,哎,你工作还没干完呢。再打个补丁,开始交换下一级。在我看来这种方法,更像循环,就是从上到下,一级级遍历。在这种情况下,if (!root) return root; 更像异常拦截,你别给我个空数据让我处理啊,所以拦截一下。

这两种思考方式,结果没什么大区别,第二种更直观简单。思考时候,可以两种结合。写出第二种,接下来在优化空间复杂度等角度,也不难发现和第一种没啥区别。

以上就是关于关于js如何递归实现反转二叉树相关的全部内容,希望对你有帮助。欢迎持续关注潘子夜个人博客(www.panziye.com),学习愉快哦!


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/front/11896.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】