国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Populating Next Right Pointers in Each

miracledan / 1137人閱讀

摘要:原題鏈接廣度優(yōu)先搜索復(fù)雜度時(shí)間空間思路相當(dāng)于是遍歷二叉樹(shù)。代碼記錄本層節(jié)點(diǎn)的個(gè)數(shù)最后一個(gè)節(jié)點(diǎn)的是,不做處理遞歸法復(fù)雜度時(shí)間空間遞歸棧空間思路由于父節(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 {
  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.
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

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).

原題鏈接

廣度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

相當(dāng)于是Level Order遍歷二叉樹(shù)。通過(guò)一個(gè)Queue來(lái)控制每層的遍歷,注意處理該層最后一個(gè)節(jié)點(diǎn)的特殊情況。此方法同樣可解第二題。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        Queue q = new LinkedList();
        if(root!=null) q.offer(root);
        while(!q.isEmpty()){
            //記錄本層節(jié)點(diǎn)的個(gè)數(shù)
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeLinkNode curr = q.poll();
                //最后一個(gè)節(jié)點(diǎn)的next是null,不做處理
                if(i < size - 1){
                    TreeLinkNode next = q.peek();
                    curr.next = next;
                }
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
        }
    }
}
遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(N) 遞歸棧空間

思路

由于父節(jié)點(diǎn)多了next指針,我們不用記錄父節(jié)點(diǎn)的父節(jié)點(diǎn)就能直到它相鄰的節(jié)點(diǎn)。對(duì)于左子節(jié)點(diǎn)來(lái)說(shuō),其next節(jié)點(diǎn)就是父節(jié)點(diǎn)的右節(jié)點(diǎn)。對(duì)于右子節(jié)點(diǎn)來(lái)說(shuō)i,其next節(jié)點(diǎn)就是父節(jié)點(diǎn)的next節(jié)點(diǎn)的左子節(jié)點(diǎn)。以此遞歸。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        //左子節(jié)點(diǎn)的next是右子節(jié)點(diǎn)
        if(root.left != null) root.left.next = root.right;
        if(root.right != null){
        //右子節(jié)點(diǎn)的next是父節(jié)點(diǎn)的next的左子節(jié)點(diǎn)
            root.right.next = root.next == null? null:root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}
雙指針?lè)?Two Pointers 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

上述兩種方法都會(huì)使用額外空間。實(shí)際上,我們可以用一個(gè)指針記錄當(dāng)前層內(nèi)遍歷到的節(jié)點(diǎn),另一個(gè)指針記錄下一層第一個(gè)節(jié)點(diǎn),來(lái)省去空間開(kāi)銷。這樣,我們可以基于上一層的next指針進(jìn)行橫向遍歷,同時(shí)遍歷到該層盡頭時(shí)又能使用記錄下的下一層第一個(gè)節(jié)點(diǎn)的指針來(lái)直接跳轉(zhuǎn)到下一層。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        //記錄該層當(dāng)前節(jié)點(diǎn)的指針,也叫做父節(jié)點(diǎn),我們通過(guò)遍歷父節(jié)點(diǎn),來(lái)連接它們的子節(jié)點(diǎn)
        TreeLinkNode p = root;
        //記錄下層第一個(gè)節(jié)點(diǎn)的指針
        TreeLinkNode first = null;
        while(p != null){
            //當(dāng)first為空時(shí),說(shuō)明剛跳轉(zhuǎn)到新的一層,需要設(shè)置下一層的第一個(gè)節(jié)點(diǎn)了
            if(first == null){
                first = p.left;
            }
            //如果有左子節(jié)點(diǎn),則其next是右子節(jié)點(diǎn),如果沒(méi)有,則遍歷結(jié)束
            //因?yàn)槲覀儗?shí)際上是將下一層的節(jié)點(diǎn)用next指針連接,所以當(dāng)遍歷到葉子結(jié)點(diǎn)時(shí)已經(jīng)沒(méi)有下一層
            if(p.left != null){
                p.left.next = p.right; 
            } else {
                break;
            }
            //如果父節(jié)點(diǎn)有next,則next的左子節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)的next,如果沒(méi)有,說(shuō)明這層遍歷完了,轉(zhuǎn)入下一層
            if(p.next != null){
                p.right.next = p.next.left;
                p = p.next;
            } else {
                p = first;
                first = null;
            }
        }
    }
}
層次遞進(jìn)法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

因?yàn)槲覀兇_定的知道每個(gè)非葉子節(jié)點(diǎn)都有左右節(jié)點(diǎn),所以我們可以一層一層鏈接。只要根據(jù)當(dāng)前層的next指針形成的鏈表,將下一層的左右左右連起來(lái)就行了。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = root;
        while(head != null){
            // 記錄當(dāng)層第一個(gè)節(jié)點(diǎn)
            TreeLinkNode tmpHead = head;
            // 開(kāi)始鏈接下一層
            while(head != null){
                //鏈接左節(jié)點(diǎn)
                if(head.left != null) head.left.next = head.right;
                //鏈接右節(jié)點(diǎn)
                if(head.right != null) head.right.next = head.next != null ? head.next.left : null;
                head = head.next;
            }
            // 跳到下一層第一個(gè)節(jié)點(diǎn)
            head = tmpHead.left;
        }
    }
}
Populating Next Right Pointers in Each Node II

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 space. For example, Given the
following binary tree,

     1
   /  
  2    3
 /     
4   5    7 

After calling your function, the tree should look like:

     1 -> NULL
   /  
  2 -> 3 -> NULL
 /     
4-> 5 -> 7 -> NULL

原題鏈接

遞歸法 復(fù)雜度

時(shí)間 O(N) 空間 O(N) 遞歸棧空間

思路

由于父節(jié)點(diǎn)多了next指針,我們不用記錄父節(jié)點(diǎn)的父節(jié)點(diǎn)就能直到它相鄰的節(jié)點(diǎn)。對(duì)于左子節(jié)點(diǎn)來(lái)說(shuō),其next節(jié)點(diǎn)就是父節(jié)點(diǎn)的右節(jié)點(diǎn)。對(duì)于右子節(jié)點(diǎn)來(lái)說(shuō)i,其next節(jié)點(diǎn)就是父節(jié)點(diǎn)的next節(jié)點(diǎn)的左子節(jié)點(diǎn)。以此遞歸。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        if(root.left != null) root.left.next = root.right;
        if(root.right != null){
            root.right.next = root.next == null? null:root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}
三指針?lè)?Three Pointers 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

當(dāng)不是完全二叉樹(shù)時(shí),左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)都有可能為空,每個(gè)葉子節(jié)點(diǎn)的深度也不一定相同,所以退出循環(huán)的條件、每層頭節(jié)點(diǎn)的確定方法以及next指針的賦值都要改變。首先,next指針不再是分左右子節(jié)點(diǎn)來(lái)直接賦值,而是對(duì)記錄下來(lái)的上個(gè)節(jié)點(diǎn)的next賦當(dāng)前操作的節(jié)點(diǎn)。其次,退出循環(huán)不能再像上一題一樣到最后一層就可以退出,因?yàn)楫?dāng)前節(jié)點(diǎn)會(huì)不斷更新,只有當(dāng)前節(jié)點(diǎn)為空時(shí)才能退出。最后頭節(jié)點(diǎn)可能是左子節(jié)點(diǎn),也可能是右子節(jié)點(diǎn)。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        TreeLinkNode p = root;
        TreeLinkNode first = null;
        //上一個(gè)節(jié)點(diǎn),我們給上一個(gè)節(jié)點(diǎn)的next賦值,然后再更新上一個(gè)節(jié)點(diǎn)為它的next
        TreeLinkNode last = null;
        while(p != null){
            //下一層的頭節(jié)點(diǎn)有可能是左子節(jié)點(diǎn)也有可能是右子節(jié)點(diǎn)
            if(first == null){
                if(p.left != null){
                    first = p.left;
                } else if(p.right != null){
                    first = p.right;
                }
            }
            //更新last和last的next
            if(p.left != null){
                if(last != null){
                    last.next = p.left;
                }
                last = p.left;
            }
            if(p.right != null){
                if(last != null){
                    last.next = p.right;
                }
                last = p.right;
            }
            //如果當(dāng)前節(jié)點(diǎn)沒(méi)有next,則該層結(jié)束,轉(zhuǎn)入下一層,否則就繼續(xù)
            if(p.next != null){
                p = p.next;
            } else {
                p = first;
                first = null;
                last = null;
            }
            
        }
    }
}
層次遞進(jìn)法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

第一問(wèn)層次遞進(jìn)的延伸。上一問(wèn)中我們不需要一個(gè)額外的指針來(lái)控制我們一層中鏈接的節(jié)點(diǎn),因?yàn)槲覀冎揽隙ㄊ亲笥易笥业捻樞颍@題中左右節(jié)點(diǎn)可能不存在,所有我們要用一個(gè)指針記錄這一層中我們鏈接到了哪個(gè)節(jié)點(diǎn),方便我們鏈接下一個(gè)節(jié)點(diǎn)。

代碼
public class Solution {
    public void connect(TreeLinkNode root) {
        // head是上一層的節(jié)點(diǎn),我們用上一層節(jié)點(diǎn)的next形成鏈表,來(lái)鏈接當(dāng)前這層
        TreeLinkNode head = root;
        while(head != null){
            // 記錄鏈接到哪個(gè)節(jié)點(diǎn)的額外指針
            TreeLinkNode curr = new TreeLinkNode(0);
            // tmp指向該層的第一節(jié)點(diǎn)
            TreeLinkNode tmp = curr;
            while(head != null){
                // 嘗試鏈接左節(jié)點(diǎn)
                if(head.left != null){
                    curr.next = head.left;
                    curr = curr.next;
                }
                // 嘗試鏈接右節(jié)點(diǎn)
                if(head.right != null){
                    curr.next = head.right;
                    curr = curr.next;
                }
                head = head.next;
            }
            // 將head移動(dòng)到當(dāng)前這層的的第一個(gè),準(zhǔn)備鏈接下一層
            head = tmp.next;
        }
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/66157.html

相關(guān)文章

  • leetcode116-117. Populating Next Right Pointers in

    摘要:題目要求給一個(gè)完全二叉樹(shù),將當(dāng)前節(jié)點(diǎn)的值指向其右邊的節(jié)點(diǎn)。而在中則是提供了一個(gè)不完全的二叉樹(shù),其它需求沒(méi)有發(fā)生改變。我們需要使用一個(gè)變量來(lái)存儲(chǔ)父節(jié)點(diǎn),再使用一個(gè)變量來(lái)存儲(chǔ)當(dāng)前操作行的,將前一個(gè)指針指向當(dāng)前父節(jié)點(diǎn)的子節(jié)點(diǎn)。 題目要求 Given a binary tree struct TreeLinkNode { TreeLinkNode *left; ...

    coolpail 評(píng)論0 收藏0
  • 117. Populating Next Right Pointers In Each NodeII

    題目: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...

    jackwang 評(píng)論0 收藏0
  • LeetCode[117] Population Next Right Pointers in Ea

    摘要:復(fù)雜度思路設(shè)置一個(gè)指向下一層要遍歷的節(jié)點(diǎn)的開(kāi)頭的位置。 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: ...

    lijinke666 評(píng)論0 收藏0
  • [LeetCode] 426. Convert BST to Sorted Doubly Linke

    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...

    MartinDai 評(píng)論0 收藏0
  • [Leetcode] Two Sum 兩數(shù)和

    摘要:如果存在該差值,說(shuō)明存在兩個(gè)數(shù)之和是目標(biāo)和。而哈希表方法中的則可以換成。如果要求的不是兩個(gè)數(shù)和和,而是找兩個(gè)數(shù)之差為特定值的配對(duì)呢同樣用哈希表可以解決。 Two Sum Given an array of integers, find two numbers such that they add up to a specific target number.The function t...

    pkhope 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<