LeetCode——Populating Next Right Pointers in Each Node II

1417 단어 LeetCode
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 space.
For example, Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
원제 링크:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
제목: 앞문제의 계속, 임의의 두 갈래 나무로 정해지면 앞문제의 코드를 사용할 수 있습니까?
사고방식: 분명히 앞의 문제는 사용할 수 없다.층계로 두루 다닐 수밖에 없다.
	public void connect(TreeLinkNode root) {
		if(root == null)
			return;
		TreeLinkNode parent = root,pre,next;
		while(parent != null){
			pre = null;
			next = null;
			while(parent != null){
				if(next == null)
					next = (parent.left == null) ? parent.right : parent.left;
				if(parent.left != null){
					if(pre != null){
						pre.next = parent.left;
						pre = pre.next;
					}else
						pre = parent.left;
				}
				if(parent.right != null){
					if(pre != null){
						pre.next = parent.right;
						pre = pre.next;
					}else
						pre = parent.right;
				}
				parent = parent.next;
			}
			parent = next;
		}
	}

좋은 웹페이지 즐겨찾기