leetcode116-117. Populating Next Right Pointers in

coolpail 發(fā)布于2019-08-15 11:07 / 3137人閱讀

摘要：題目要求給一個(gè)完全二叉樹，將當(dāng)前節(jié)點(diǎn)的值指向其右邊的節(jié)點(diǎn)。而在中則是提供了一個(gè)不完全的二叉樹，其它需求沒有發(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;
      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è)變量來(lái)存儲(chǔ)父節(jié)點(diǎn)，再使用一個(gè)變量來(lái)存儲(chǔ)當(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)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~