唔，今天陽光正好，微風(fēng)不燥。我站在陽臺(tái)吹了好久的風(fēng)，也沒看清以后的路。
閑話不提，先把今日份的三道題刷完。
二叉樹展開為鏈表
題目：給定一個(gè)二叉樹，原地將它展開為鏈表。
思路：講真，我覺得這個(gè)題目的重點(diǎn)是原地展開吧。本來一審題覺得是個(gè)蠻簡(jiǎn)單的題目。。后來看了已給代碼覺得也沒想的那么簡(jiǎn)單。單純展開就是一個(gè)前序排列的結(jié)果，但是說到原地。。。嘖嘖嘖，我可能是題意沒太理解，我先照著想的試試代碼吧。
回來了，我也不知道為啥看著挺簡(jiǎn)單的一道題我寫的這么惡心，反正是實(shí)現(xiàn)了，我先貼出來：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if(root==null) return;
TreeNode cur = root;
LinkedList<Integer> pre = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(cur !=null || !stack.isEmpty()){
if(cur!=null){
pre.add(cur.val);
stack.add(cur);
cur = cur.left;
}else{
cur = stack.pop();
cur = cur.right;
}
}
pre.removeFirst();
for(int i : pre){
root.left = null;
root.right = new TreeNode(i);
root = root.right;
}
}
}
如上代碼，先前序遍歷，然后重新改變r(jià)oot的構(gòu)造，也不知道算不算在原地更改的，畢竟沒有直接root=新樹。。。真的我現(xiàn)在才發(fā)現(xiàn)我對(duì)于很多題目上的要求不是很懂，我直接去看看人家的代碼吧。
看到了一種很優(yōu)雅的代碼，是遞歸實(shí)現(xiàn)的，我這里先中序再一個(gè)個(gè)掛很麻煩，其實(shí)這個(gè)題可以直接掛，掛的準(zhǔn)則跟中序差不多，對(duì)于每一個(gè)非葉子節(jié)點(diǎn)來說，先把右節(jié)點(diǎn)保存，然后左節(jié)點(diǎn)掛在右節(jié)點(diǎn)的位置上，左節(jié)點(diǎn)清空，然后指針往下指到最下面的葉子節(jié)點(diǎn)，再把之前保存的右節(jié)點(diǎn)掛上。說起來很復(fù)雜，其實(shí)我畫個(gè)草圖就好明白了:
其實(shí)這個(gè)是比較無腦的草圖，可以摳細(xì)節(jié)，比如如果本來左節(jié)點(diǎn)就沒有了，則不需要操作了。其次我這里簡(jiǎn)單的root = root.right.但是如果左節(jié)點(diǎn)本身不是葉子節(jié)點(diǎn)是應(yīng)該繼續(xù)處理的。這里應(yīng)該直接指到當(dāng)前的葉子節(jié)點(diǎn)再操作，應(yīng)該用while一直指到最后一個(gè)節(jié)點(diǎn)。但是大體思路就是這么個(gè)過程。我直接貼大神代碼了：
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
root.left = null;
while(root.right != null) root = root.right;
root.right = tmp;
}
}
喏，就是我又壓棧又遍歷又重新各種建樹的，，，人家這么幾行代碼，，簡(jiǎn)潔明了，真的大寫的服。哈哈，下一題了。
填充每一個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
題目：給定一個(gè)完美二叉樹，其所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。
提示：
你只能使用常量級(jí)額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復(fù)雜度。
思路：首先這個(gè)題目很長，所以有點(diǎn)考驗(yàn)我的閱讀能力，其次提示中遞歸解題符合要求，說明這道題用遞歸是一個(gè)思路。第一反應(yīng)是這個(gè)，然后正兒八經(jīng)解題思路是遍歷樹，然后同一層的除了最后一個(gè)分別把next給加上。因?yàn)樯婕暗絥ext是每一層的右邊那個(gè)節(jié)點(diǎn)，所以我覺得應(yīng)該是層次遍歷。但是題目說了要常量額外空間，這就有點(diǎn)難了，具體怎么實(shí)現(xiàn)我去嘗試寫寫代碼。
有點(diǎn)煩躁?。?！遞歸是遞歸了，但是我還是覺得我用額外空間了，，，藍(lán)瘦：
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null) return root;
List<Node> l = new ArrayList<Node>();
l.add(root);
dfs(l);
return root;
}
public void dfs(List<Node> list){
if(list.size()==0) return;
List<Node> l = new ArrayList<Node>();
for(int i = 0;i<list.size()-1;i++){
list.get(i).next = list.get(i+1);
if(list.get(i).left!=null)l.add(list.get(i).left);
if(list.get(i).right!=null)l.add(list.get(i).right);
}
if(list.get(list.size()-1).left!=null)l.add(list.get(list.size()-1).left);
if(list.get(list.size()-1).right!=null)l.add(list.get(list.size()-1).right);
dfs(l);
}
}
而且自己都覺得寫得惡心，其實(shí)一個(gè)顯示隊(duì)列的調(diào)用能直接解決問題，，，我也不知道這么多此一舉各種麻煩算不算是符合題目要求的。。。難受，我決定用我自己的方式好好寫一下代碼，至于額外空間，我到時(shí)候還是看題解吧。我去寫我自己滿意的版本了：
class Solution {
public Node connect(Node root) {
if(root==null) return root;
Queue<Node> quque = new LinkedBlockingQueue<Node>();
quque.add(root);
while(!quque.isEmpty()){
int size = quque.size();
for(int i = 0;i<size;i++){
Node n = quque.poll();
if(i!=size-1)n.next = quque.peek();
if(n.left!=null)quque.add(n.left);
if(n.right!=null) quque.add(n.right);
}
}
return root;
}
}
咳，反正我自認(rèn)為代碼是優(yōu)雅了，就是性能沒法看了，，，我直接看性能排行第一的代碼了。
！?。?！看完人家的代碼我覺得自己可能是個(gè)傻子。。這個(gè)題簡(jiǎn)單的出人意料??！我之前一直陷入一個(gè)誤區(qū)，就是一個(gè)根節(jié)點(diǎn)的左右節(jié)點(diǎn)是可以找到下一個(gè)的，但是如果是相差很多節(jié)點(diǎn)的，需要右節(jié)點(diǎn)連接子節(jié)點(diǎn)要怎么找到呢，然后就卡死在這，都是每一層每一層的遍歷。?！，F(xiàn)在看了人家的代碼才發(fā)現(xiàn)，其實(shí)從父節(jié)點(diǎn)的next就可以獲取當(dāng)前節(jié)點(diǎn)的next。。。我真的是，這個(gè)就是思路問題，我去重寫了。
class Solution {
public Node connect(Node root) {
if(root==null) return root;
if(root.left!=null && root.right!=null){
root.left.next = root.right;
if(root.next!=null){
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
}
return root;
}
}
直接貼代碼并自閉五分鐘。。。下一題了。
題目：給定一個(gè)二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。
進(jìn)階：
你只能使用常量級(jí)額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復(fù)雜度。
題目截圖
思路：額，這個(gè)題和上個(gè)題，除了不完美就沒別的了，但是感覺不能沿用上面的代碼了，因?yàn)榕袛嗌弦粋€(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)可能就輪空了，我畫個(gè)草圖。所以怎么處理我還是要想想，其實(shí)感覺判斷下一個(gè)節(jié)點(diǎn)如果是葉子節(jié)點(diǎn)則繼續(xù)往下判斷就行了。不過這么想的話，判斷有點(diǎn)多啊，不是實(shí)現(xiàn)不了，我先去試試。
好了，其實(shí)在第一道題的基礎(chǔ)上改動(dòng)思路還是好很多的，我直接貼代碼：
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root==null) return root;
if(root.right!=null){
if(root.left!=null) root.left.next = root.right;
if( root.next!= null){//右節(jié)點(diǎn)連下一個(gè)節(jié)點(diǎn)
root.right.next = nextNode(root.next);
}
}else if(root.left!=null){
if( root.next!= null){//沒有右節(jié)點(diǎn)則直接左節(jié)點(diǎn)連下一個(gè)節(jié)點(diǎn)
root.left.next = nextNode(root.next);
}
}
connect(root.right);
connect(root.left);
return root;
}
//獲取下一個(gè)節(jié)點(diǎn)
private Node nextNode(Node node) {
while (node != null) {
if (node.left != null) {
return node.left;
}
if (node.right != null) {
return node.right;
}
node = node.next;
}
return null;
}
}
因?yàn)槲矣X得不是很難，所以也沒啥好講的，這個(gè)和上一道題比就是條件判斷多了而已。哦，對(duì)了有一點(diǎn)就是先遞歸右節(jié)點(diǎn)再遞歸左節(jié)點(diǎn)。
這個(gè)順序仔細(xì)想想就能知道為什么。因?yàn)槭沁f歸，如果先遞歸左節(jié)點(diǎn)，到了需要右節(jié)點(diǎn)底下的節(jié)點(diǎn)時(shí)就沒了。這樣會(huì)丟失指向。我在畫個(gè)圖。
- 如圖所示，第一個(gè)遞歸，把標(biāo)1的指向指向好了。
- 第二次遞歸，根節(jié)點(diǎn)變成了紫色節(jié)點(diǎn)，然后把兩個(gè)紅色節(jié)點(diǎn)的指向做好了，也就是標(biāo)做2的線。
- 第三次遞歸，先左后右的話，左邊紅色節(jié)點(diǎn)作為根節(jié)點(diǎn)，吧兩個(gè)藍(lán)色節(jié)點(diǎn)指向做好了。
- 重點(diǎn)來了，第四次遞歸，因?yàn)樽筮叡闅v完了，該右節(jié)點(diǎn)，所以根節(jié)點(diǎn)是右邊紅色節(jié)點(diǎn)（葉子節(jié)點(diǎn)直接pass了），這個(gè)時(shí)候兩個(gè)黃節(jié)點(diǎn)之間的線可以連，但是第二黃色節(jié)點(diǎn)從父節(jié)點(diǎn)找到的那個(gè)節(jié)點(diǎn)沒有子節(jié)點(diǎn)，再往下找線沒連呢。。。所以就自動(dòng)以為沒節(jié)點(diǎn)了。所以錯(cuò)誤就來了。
額，說這么多是為了解釋為什么必須先遞歸右節(jié)點(diǎn)而不是常規(guī)的左節(jié)點(diǎn)。。所以這個(gè)題就這樣了。
今天的筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注，也祝大家工作順順利利！生活健健康康??！另外周末愉快！
