leetcode116-117. Populating Next Right Pointers in

coolpail 发布于2019-08-15 11:07 / 3014人阅读

摘要：题目要求给一个完全二叉树，将当前节点的值指向其右边的节点。而在中则是提供了一个不完全的二叉树，其它需求没有发生改变。我们需要使用一个变量来存储父节点，再使用一个变量来存储当前操作行的，将前一个指针指向当前父节点的子节点。

题目要求

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

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云服务器托管 Populating Pointers right two-pointers

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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