LeetCode[117] Population Next Right Pointers in Ea

lijinke666 发布于2019-08-14 15:06 / 2078人阅读

摘要：复杂度思路设置一个指向下一层要遍历的节点的开头的位置。

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:
     1 -> NULL
   /  
  2 -> 3 -> NULL
 /     
4-> 5 -> 7 -> NULL

Iteration

复杂度
O(N),O(1)

思路
设置一个dummy node 指向下一层要遍历的节点的开头的位置。

代码

public void connect(TreeLinkNode root) {
    TreeLinkNode dummy = new TreeLinkNode(0);
    TreeLinkNode pre = dummy;
    while(root != null) {
        if(root.left != null) {
            pre.next = root.left;
            pre = pre.next;
        }
        if(root.right != null) {
            pre.next = root.right;
            pre = pre.next;
        }
        root = root.next;
        // done with the search of current level
        if(root == null) {
            root = dummy.next;
            pre = dummy;
            dummy.next = null;
        }
    }

}

云服务器 GPU云服务器 Population cdn117 Pointers right

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

转载请注明本文地址：https://www.ucloud.cn/yun/65292.html

leetcode116-117. Populating Next Right Pointers in

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

coolpail 2019-08-15 11:07 评论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] 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
[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] 289. Game of Life

Problem According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. Given a board with m ...

Ajian 2019-08-19 11:16 评论0 收藏0