首頁猿問關(guān)于遞歸的理解？

關(guān)于遞歸的理解？

JavaScript

一只萌萌小番薯 2019-04-21 20:14:42

varinvertTree=function(root){if(root===null)returnnull;vartemp=root.left;root.left=invertTree(root.right);root.right=invertTree(temp);returnroot;};varinvertTree=function(root){if(root===null)return;//swapleftandrightchildvartemp=root.left;root.left=root.right;root.right=temp;//recurseintochildreninvertTree(root.left);invertTree(root.right);};這兩個程序的遞歸細節(jié)是一樣的嗎？

查看完整描述

2 回答

森林海

TA貢獻2011條經(jīng)驗獲得超2個贊

不明白難點在哪里……這不就是大名鼎鼎的反轉(zhuǎn)二叉樹么……如果你明白什么是反轉(zhuǎn)二叉數(shù)的話，那應(yīng)該很容易理解，我們要做的就是把每個節(jié)點的leftchild和rightchild互換。在JavaScript里swap兩個變量需要手動寫臨時變量temp。而要遍歷每個節(jié)點做這樣的處理，遞歸到它的children是必要的。事實上在這個case里，invertTree函數(shù)沒有必要有返回值，因為它返回的就是它的參數(shù)root。所以加上返回值可能反而有點confusion。也許像下面這么寫反而更容易看懂：varinvertTree=function(root){if(root===null)return;//swapleftandrightchildvartemp=root.left;root.left=root.right;root.right=temp;//recurseintochildreninvertTree(root.left);invertTree(root.right);};