FilesExpand file tree

 master

/

NextRightPointer.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (69 loc) · 2.29 KB

 master

/

NextRightPointer.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (69 loc) · 2.29 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

package tree;

import java.util.ArrayDeque;

import java.util.Queue;

/**

* Created by gouthamvidyapradhan on 07/07/2017.

*

* <p>Given a binary tree

*

* <p>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.

*

* <p>Initially, all next pointers are set to NULL.

*

* <p>Note:

*

* <p>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

*

* <p>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));

}

}

}