摘要:翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開(kāi)始不是很清楚,但是里面的高票答案給了一個(gè)很好的解釋。看例子,樹(shù)的左邊最深的底層是,是新的。對(duì)于每個(gè),將鏈接右孩子的指針去掉,將變?yōu)楫?dāng)前左孩子的,成為左孩子的。遞歸的寫(xiě)法遞歸調(diào)用得到新的,并且沿途改變結(jié)構(gòu)。
LeetCode 156 Binary Tree Upside Down
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
Example:
Input: [1,2,3,4,5]
1 / 2 3 / 4 5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
翻轉(zhuǎn)以后如下:
4 / 5 2 / 3 1
解題思路:
翻轉(zhuǎn)的形式一開(kāi)始不是很清楚,但是discuss里面的高票答案給了一個(gè)很好的解釋。看例子,樹(shù)的左邊最深的底層是4,4是新的root。對(duì)于每個(gè)root node,將鏈接右孩子的指針去掉,將root node變?yōu)楫?dāng)前左孩子的left node,root node成為左孩子的right node。
1 / x 2 -- 3 / x 4 -- 5 ^ new root
遞歸的寫(xiě)法:
public TreeNode upsideDownBinaryTree(TreeNode root) { if (root == null || root.left == null) { return root; } //遞歸調(diào)用得到新的root,并且沿途改變結(jié)構(gòu)。 TreeNode newRoot = upsideDownBinaryTree(root.left); root.left.left = root.right; root.left.right = root; //千萬(wàn)記得將root node 的左右兩邊設(shè)為null root.left = null; root.right = null; return newRoot; }
遍歷的解法
遍歷的解法需要四個(gè)指針,如圖所示,每次先update next,然后對(duì)swap上一個(gè)node的右孩子和這個(gè)node的左孩子,所以每次我們需要一個(gè)temp來(lái)記錄上一個(gè)node的右邊孩子。
prev -> 1 / x curr -> 2 -- 3 <-temp / x next-> 4 -- 5 ^ new root
代碼如下
public TreeNode upsideDownBinaryTree(TreeNode root) { //iterative TreeNode curr = root; TreeNode prev = null; TreeNode next = null; TreeNode temp = null; while(curr != null) { next = curr.left; //swap nodes, we need to keep a temp to track the right node curr.left = temp; temp = curr.right; curr.right = prev; prev = curr; curr = next; } return prev;
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/71794.html
摘要:原題鏈接遞歸法復(fù)雜度時(shí)間空間遞歸棧空間思路這個(gè)難倒大神的題也是非常經(jīng)典的一道測(cè)試對(duì)二叉樹(shù)遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點(diǎn)或葉子節(jié)點(diǎn)時(shí),不再交換,直接返回該節(jié)點(diǎn)。代碼給出的是后序遍歷的自下而上的交換,先序遍歷的話就是自上而下的交換。 Invert Binary Tree Invert a binary tree. 4 / 2 7 / ...
摘要:算法思路判斷樹(shù)是否為空同時(shí)也是終止條件。分別對(duì)左右子樹(shù)進(jìn)行遞歸。代碼實(shí)現(xiàn)判斷當(dāng)前樹(shù)是否為左右子樹(shù)結(jié)點(diǎn)交換分別對(duì)左右子樹(shù)進(jìn)行遞歸返回樹(shù)的根節(jié)點(diǎn)歡迎一起加入到開(kāi)源倉(cāng)庫(kù),可以向提交您其他語(yǔ)言的代碼。 Time:2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿 題目:Invert Binary Tree(反轉(zhuǎn)二叉樹(shù)) ...
LeetCode 104 Maximum Depth of Binary Tree難度:Easy 題目描述:找到一顆二叉樹(shù)的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...
摘要:在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語(yǔ)言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號(hào): showImg(htt...
閱讀 1924·2021-11-19 09:40
閱讀 2132·2021-10-09 09:43
閱讀 3294·2021-09-06 15:00
閱讀 2810·2019-08-29 13:04
閱讀 2766·2019-08-26 11:53
閱讀 3512·2019-08-26 11:46
閱讀 2320·2019-08-26 11:38
閱讀 390·2019-08-26 11:27