java面試題解LeetCode27二叉樹的鏡像實(shí)例
正文
LeetCode27. 二叉樹的鏡像 請完成一個函數(shù),輸入一個二叉樹,該函數(shù)輸出它的鏡像。
例如輸入:
4
/
2 7 / \ /
1 3 6 9 鏡像輸出:
4
/
7 2 / \ /
9 6 3 1
示例 1: 輸入:root = [4,2,7,1,3,6,9] 輸出:[4,7,2,9,6,3,1]
限制: 0 <= 節(jié)點(diǎn)個數(shù) <= 1000
解題思路
方法一:遞歸法
根據(jù)二叉樹鏡像的定義,考慮遞歸遍歷(dfs)二叉樹,交換每個節(jié)點(diǎn)的左 / 右子節(jié)點(diǎn),即可生成二叉樹的鏡像。 遞歸解析: 終止條件: 當(dāng)節(jié)點(diǎn) rootroot 為空時(shí)(即越過葉節(jié)點(diǎn)),則返回 nullnull ; 遞推工作: 初始化節(jié)點(diǎn) tmptmp ,用于暫存 rootroot 的左子節(jié)點(diǎn); 開啟遞歸 右子節(jié)點(diǎn) mirrorTree(root.right)mirrorTree(root.right) ,并將返回值作為 rootroot 的 左子節(jié)點(diǎn) 。 開啟遞歸 左子節(jié)點(diǎn) mirrorTree(tmp)mirrorTree(tmp) ,并將返回值作為 rootroot 的 右子節(jié)點(diǎn) 。 返回值: 返回當(dāng)前節(jié)點(diǎn) rootroot ;
Q: 為何需要暫存 rootroot 的左子節(jié)點(diǎn)? A: 在遞歸右子節(jié)點(diǎn) “root.left = mirrorTree(root.right);root.left=mirrorTree(root.right);” 執(zhí)行完畢后, root.leftroot.left 的值已經(jīng)發(fā)生改變,此時(shí)遞歸左子節(jié)點(diǎn) mirrorTree(root.left)mirrorTree(root.left) 則會出問題。
class Solution { public TreeNode mirrorTree(TreeNode root) { if(root == null) return null; TreeNode tmp = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(tmp); return root; } }
方法二:輔助棧(或隊(duì)列)
利用棧(或隊(duì)列)遍歷樹的所有節(jié)點(diǎn) nodenode ,并交換每個 nodenode 的左 / 右子節(jié)點(diǎn)。 算法流程: 特例處理: 當(dāng) rootroot 為空時(shí),直接返回 nullnull ; 初始化: 棧(或隊(duì)列),本文用棧,并加入根節(jié)點(diǎn) rootroot 。 循環(huán)交換: 當(dāng)棧 stackstack 為空時(shí)跳出; 出棧: 記為 nodenode ; 添加子節(jié)點(diǎn): 將 nodenode 左和右子節(jié)點(diǎn)入棧; 交換: 交換 nodenode 的左 / 右子節(jié)點(diǎn)。 返回值: 返回根節(jié)點(diǎn) rootroot 。
class Solution { public TreeNode mirrorTree(TreeNode root) { if(root == null) return null; Stack<TreeNode> stack = new Stack<>() {{ add(root); }}; while(!stack.isEmpty()) { TreeNode node = stack.pop(); if(node.left != null) stack.add(node.left); if(node.right != null) stack.add(node.right); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; } return root; } }
以上就是java面試題解LeetCode27二叉樹的鏡像實(shí)例的詳細(xì)內(nèi)容,更多關(guān)于java面試LeetCode二叉樹鏡像的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
java poi導(dǎo)出excel時(shí)如何設(shè)置手動換行
這篇文章主要介紹了java poi導(dǎo)出excel時(shí)如何設(shè)置手動換行,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-06-06JFrame中添加和設(shè)置JPanel的方法實(shí)例解析
這篇文章主要介紹了JFrame中添加和設(shè)置JPanel的方法實(shí)例解析,具有一定借鑒價(jià)值2018-01-01mybatis實(shí)現(xiàn)一對一關(guān)聯(lián)映射實(shí)例代碼
這篇文章主要給大家介紹了關(guān)于mybatis實(shí)現(xiàn)一對一關(guān)聯(lián)映射的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11一文解決System.in關(guān)閉后無法再繼續(xù)使用流的問題
這篇文章主要給大家介紹如何解決System.in關(guān)閉后無法再繼續(xù)使用流的問題,文中有詳細(xì)的解決方法和代碼示例,具有一定的參考價(jià)值,需要的朋友可以參考下2023-07-07try-with-resource優(yōu)雅關(guān)閉io流的方法
這篇文章主要給大家介紹了關(guān)于try-with-resource優(yōu)雅關(guān)閉io流的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01三分鐘讀懂mybatis中resultMap和resultType區(qū)別
這篇文章主要給大家介紹了mybatis中resultMap和resultType區(qū)別的相關(guān)資料,resultType和resultMap都是mybatis進(jìn)行數(shù)據(jù)庫連接操作處理返回結(jié)果的,需要的朋友可以參考下2023-07-07