leetcode116-117. Populating Next Right Pointers in

coolpail 發布于2019-08-15 11:07 / 3143人閱讀

摘要：題目要求給一個完全二叉樹，將當前節點的值指向其右邊的節點。而在中則是提供了一個不完全的二叉樹，其它需求沒有發生改變。我們需要使用一個變量來存儲父節點，再使用一個變量來存儲當前操作行的，將前一個指針指向當前父節點的子節點。

題目要求

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

給一個完全二叉樹，將當前節點的next值指向其右邊的節點。
而在II中則是提供了一個不完全的二叉樹，其它需求沒有發生改變。
額外的需求包括O(1）的空間復雜度

思路和代碼

這里其實是水平遍歷（level traversal）的一種實現。我們需要使用一個變量來存儲父節點，再使用一個變量來存儲當前操作行的，將前一個指針指向當前父節點的子節點。

    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;
        }
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Populating Pointers right two-pointers

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67548.html

[Leetcode] Populating Next Right Pointers in Each

摘要：原題鏈接廣度優先搜索復雜度時間空間思路相當于是遍歷二叉樹。代碼記錄本層節點的個數最后一個節點的是，不做處理遞歸法復雜度時間空間遞歸棧空間思路由于父節點多了指針，我們不用記錄父節點的父節點就能直到它相鄰的節點。 Populating Next Right Pointers in Each Node I Given a binary tree struct TreeLinkNode { ...

miracledan 2019-08-14 16:10 評論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 2019-08-14 14:13 評論0 收藏0
LeetCode[117] Population Next Right Pointers in Ea

摘要：復雜度思路設置一個指向下一層要遍歷的節點的開頭的位置。 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 2019-08-14 15:06 評論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 2019-08-16 13:28 評論0 收藏0
[LeetCode] 430. Flatten a Multilevel Doubly Linked

摘要： 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...

curried 2019-08-16 13:50 評論0 收藏0