資訊專(zhuān)欄INFORMATION COLUMN
Problem
Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in ListNode.
1
1 2
/
2 5 => 3
/
3 4 6 4
5
6
Solution
neat and beautiful
public class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
TreeNode left = root.left;
TreeNode right = root.right;
flatten(left);
flatten(right);
root.left = null;
root.right = left;
TreeNode cur = root;
while (cur.right != null) cur = cur.right;
cur.right = right;
}
}
Use stack
public void flatten(TreeNode root) {
Stack stack = new Stack();
TreeNode p = root;
while(p != null || !stack.empty()){
if(p.right != null){
stack.push(p.right);
}
if(p.left != null){
p.right = p.left;
p.left = null;
}
else if(!stack.empty()){
TreeNode temp = stack.pop();
p.right=temp;
}
p = p.right;
}
}
Update 2018-11
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right);
flatten(root.left);
TreeNode right = root.right;
TreeNode left = root.left;
if (left != null) {
root.left = null;
root.right = left;
while (left.right != null) left = left.right;
left.right = right;
}
return;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65443.html
摘要：題目要求將一棵二叉樹(shù)展開(kāi)形成一棵鏈表形狀的樹(shù)。本質(zhì)上是將該樹(shù)轉(zhuǎn)變成先序遍歷后的樣子。所以這個(gè)例題一步步的操作如下代碼如下思路二遞歸其實(shí)這里的思路等價(jià)于反轉(zhuǎn)的先序遍歷。自底向上深度優(yōu)先遍歷，這要求將前序遍歷的頭結(jié)點(diǎn)通過(guò)臨時(shí)變量保存一下。 題目要求 Given a binary tree, flatten it to a linked list in-place. For example...
摘要：思路這題相當(dāng)于是當(dāng)?shù)臅r(shí)候，關(guān)鍵是要知道要被連接的的前面的一個(gè)這樣才可以把接上。用一路做到底，當(dāng)做到的時(shí)候，左邊返回右邊也返回，這時(shí)返回自己成為同樣接著繼續(xù)做。 Flatten Binary Tree to Linked List Flatten a binary tree to a fake linked list in pre-order traversal.Here we use ...
摘要：棧法復(fù)雜度時(shí)間空間思路對(duì)于一個(gè)根節(jié)點(diǎn)，我們將它的右子樹(shù)壓進(jìn)一個(gè)棧中，然后將它的左子樹(shù)放到右邊來(lái)。如果該節(jié)點(diǎn)沒(méi)有左子樹(shù)，說(shuō)明該節(jié)點(diǎn)是某個(gè)左子樹(shù)的最后一個(gè)節(jié)點(diǎn)，我們這時(shí)候把棧中最近的右子樹(shù)出來(lái)接到它的右邊。 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-plac...
摘要：解法真的非常巧妙，不過(guò)這道題里仍要注意兩個(gè)細(xì)節(jié)。中，為時(shí)，返回長(zhǎng)度為的空數(shù)組建立結(jié)果數(shù)組時(shí)，是包括根節(jié)點(diǎn)的情況，是不包含根節(jié)點(diǎn)的情況。而非按左右子樹(shù)來(lái)進(jìn)行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...
Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...
閱讀 3151·2021-11-08 13:18
閱讀 2291·2019-08-30 15:55
閱讀 3614·2019-08-30 15:44
閱讀 3075·2019-08-30 13:07
閱讀 2786·2019-08-29 17:20
閱讀 1953·2019-08-29 13:03
閱讀 3419·2019-08-26 10:32
閱讀 3231·2019-08-26 10:15
