leetcode/problems/src/tree/NextRightPointer.java at master · KindleBooks66/leetcode · GitHub

History

76 lines (69 loc) · 2.29 KB

Raw

package tree;

import java.util.ArrayDeque;

import java.util.Queue;

/**

* Created by gouthamvidyapradhan on 07/07/2017.

* 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

* Solution: Perform a level order traversal using BFS, keep track of prev node at each level.

* Link the prev node to current node if both the nodes are in the same level.

public class NextRightPointer {

private class LevelNode {

int level;

TreeLinkNode node;

LevelNode(TreeLinkNode node, int level) {

this.node = node;

this.level = level;

}

public static class TreeLinkNode {

int val;

TreeLinkNode left, right, next;

TreeLinkNode(int x) {

val = x;

}

public static void main(String[] args) throws Exception {

TreeLinkNode node = new TreeLinkNode(2);

node.left = new TreeLinkNode(1);

node.right = new TreeLinkNode(3);

new NextRightPointer().connect(node);

System.out.println(node.next);

System.out.println(node.left.next.val);

System.out.println(node.right.next);

}

public void connect(TreeLinkNode root) {

Queue<LevelNode> queue = new ArrayDeque<>();

LevelNode zero = new LevelNode(root, 0);

queue.offer(zero);

LevelNode prev = null;

while (!queue.isEmpty()) {

LevelNode levelNode = queue.poll();

if (levelNode.node == null) break;

TreeLinkNode curr = levelNode.node;

if (prev != null) {

if (prev.level == levelNode.level) {

prev.node.next = levelNode.node;

}

prev = levelNode;

queue.offer(new LevelNode(curr.left, levelNode.level + 1));

queue.offer(new LevelNode(curr.right, levelNode.level + 1));

}

leetcode/problems/src/tree/NextRightPointer.java at master · KindleBooks66/leetcode · GitHub

Uh oh!

Expand file tree

Breadcrumbs

NextRightPointer.java

Latest commit

History

Breadcrumbs

NextRightPointer.java

File metadata and controls