資訊專欄INFORMATION COLUMN
摘要：題目要求給一個(gè)完全二叉樹，將當(dāng)前節(jié)點(diǎn)的值指向其右邊的節(jié)點(diǎn)。而在中則是提供了一個(gè)不完全的二叉樹，其它需求沒有發(fā)生改變。我們需要使用一個(gè)變量來存儲父節(jié)點(diǎn)，再使用一個(gè)變量來存儲當(dāng)前操作行的，將前一個(gè)指針指向當(dāng)前父節(jié)點(diǎn)的子節(jié)點(diǎn)。
題目要求
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/
2 3
/ /
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/
2 -> 3 -> NULL
/ /
4->5->6->7 -> NULL
給一個(gè)完全二叉樹，將當(dāng)前節(jié)點(diǎn)的next值指向其右邊的節(jié)點(diǎn)。
而在II中則是提供了一個(gè)不完全的二叉樹，其它需求沒有發(fā)生改變。
額外的需求包括O(1）的空間復(fù)雜度
這里其實(shí)是水平遍歷（level traversal）的一種實(shí)現(xiàn)。我們需要使用一個(gè)變量來存儲父節(jié)點(diǎn)，再使用一個(gè)變量來存儲當(dāng)前操作行的，將前一個(gè)指針指向當(dāng)前父節(jié)點(diǎn)的子節(jié)點(diǎn)。
public void connect(TreeLinkNode root) {
TreeLinkNode head = root;
TreeLinkNode prev = null;
TreeLinkNode nextHead = null;
while(head!=null){
while(head!=null){
if(head.left!=null){
if(prev!=null){
prev.next = head.left;
}else{
nextHead = head.left;
}
prev = head.left ;
}
if(head.right!=null){
if(prev!=null){
prev.next = head.right;
}else{
nextHead = head.right;
}
prev = head.right ;
}
head = head.next;
}
head = nextHead;
prev = null;
nextHead = null;
}
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/67548.html
摘要：原題鏈接廣度優(yōu)先搜索復(fù)雜度時(shí)間空間思路相當(dāng)于是遍歷二叉樹。代碼記錄本層節(jié)點(diǎn)的個(gè)數(shù)最后一個(gè)節(jié)點(diǎn)的是，不做處理遞歸法復(fù)雜度時(shí)間空間遞歸?？臻g思路由于父節(jié)點(diǎn)多了指針，我們不用記錄父節(jié)點(diǎn)的父節(jié)點(diǎn)就能直到它相鄰的節(jié)點(diǎn)。 Populating Next Right Pointers in Each Node I Given a binary tree struct TreeLinkNode { ...
題目：Follow up for problem Populating Next Right Pointers in Each Node. What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra sp...
摘要：復(fù)雜度思路設(shè)置一個(gè)指向下一層要遍歷的節(jié)點(diǎn)的開頭的位置。 LeetCode[117] Population Next Right Pointers in Each Node II 1 / 2 3 / 4 5 7 After calling your function, the tree should look like: ...
Problem Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Lets take the foll...
摘要： Problem You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These...
閱讀 3704·2021-11-24 09:39
閱讀 838·2019-08-30 14:22
閱讀 3080·2019-08-30 13:13
閱讀 2384·2019-08-29 17:06
閱讀 3004·2019-08-29 16:22
閱讀 1311·2019-08-29 10:58
閱讀 2496·2019-08-26 13:47
閱讀 1682·2019-08-26 11:39
