What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
Given the following binary tree,
1 / \ 2 3 / \ \ 4 5 7After calling your function, the tree should look like:
1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL
/** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; * TreeLinkNode left, right, next; * TreeLinkNode(int x) { val = x; } * } */ public class Solution { public void connect(TreeLinkNode root) { if(root == null) return; ArrayList<TreeLinkNode> q = new ArrayList<TreeLinkNode>(); q.add(root); while(!q.isEmpty()) { ArrayList<TreeLinkNode> next = new ArrayList<TreeLinkNode>(); for(int i = 0; i < q.size(); i++) { TreeLinkNode node = q.get(i); if(node.left != null) next.add(node.left); if(node.right != null) next.add(node.right); if(i == q.size() - 1) node.next = null; else node.next = q.get(i + 1); } q = new ArrayList<TreeLinkNode>(next); } } }
No comments:
Post a Comment