日韩福利一区二区三区,体内射精免费视频,成人视频免费观看18,中国黄色电影一级片,高清无码免费视频在线,国产又粗又猛又爽又黄91,先锋成人电影,国产午夜在线观看

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?二叉樹展開為鏈表，我們先來看題面：

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

Given a binary tree, flatten it to a linked list in-place.

題意

給定一個二叉樹，原地將它展開為一個單鏈表。

樣例

解題

https://www.cnblogs.com/gongyanzh/p/12901595.html

將左子樹插入到右子樹的地方

將原來的右子樹接到左子樹的最右邊節(jié)點

考慮新的右子樹的根節(jié)點，一直重復上邊的過程，直到新的右子樹為 null

? ? ?1
???/? \
??2???5
?/ \? ? ?\
3??4? ? ?6

//將 1 的左子樹插入到右子樹的地方
????1
?????\
? ? ? ?2? ? ? 5
?????/?\? ? ?\
????3???4????6????????
//將原來的右子樹接到左子樹的最右邊節(jié)點
????1
?????\
??????2??????????
?????/ \ 
????3???4??
?????????\
??????????5
???????????\
????????????6
????????????
?//將 2 的左子樹插入到右子樹的地方
????1
?????\
??????2??????????
???????\ 
????????3???????4??
?????????????????\
??????????????????5
???????????????????\
????????????????????6???
????????
?//將原來的右子樹接到左子樹的最右邊節(jié)點
????1
?????\
??????2??????????
???????\ 
????????3??????
?????????\
??????????4??
???????????\
????????????5
?????????????\
??????????????6

思路看上面，代碼實現(xiàn)：

class?Solution?{
????public?void?flatten(TreeNode root) {
????????//將左子樹接到右子樹 root.right = root.left
????????//為了做到這一點，首先要把右子樹移走，移到哪？移到左子樹的右子樹
????????//pre = root.left; pre.right = root.right;
????????while(root != null){
????????????//左子樹為空，直接考慮下個節(jié)點
????????????if(root.left == null){
????????????????root = root.right;
????????????}else{
????????????????TreeNode pre = root.left;
????????????????while(pre.right != null){
????????????????????pre = pre.right;
????????????????}
????????????????pre.right = root.right;
????????????????root.right = root.left;
????????????????root.left = null;
????????????????root = root.right;
????????????}
????????}
????}
}