LeetCode——Populating Next Right Pointers in Each Node

1649 단어 LeetCode
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
원제 링크:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
제목: 두 갈래 트리 (완전 두 갈래 트리라고 가정) 를 정하고 각 노드의 넥스트 바늘을 오른쪽 노드로 가리킨다.
사고방식: 먼저 떠오르는 것은 나무를 층층이 훑어보는 동시에 노드가 오른쪽 노드에 대한 지침을 추가하는 것이다.
또 다른 간결한 방법은 귀속을 통해 실현하고 간단명료하게 직관적으로 하는 것이다.
	public void connect(TreeLinkNode root) {
		if (root == null)
			return;
		if (root.left != null)
			root.left.next = root.right;
		if (root.right != null)
			root.right.next = root.next == null ? null : root.next.left;
		connect(root.left);
		connect(root.right);
	}

	// Definition for binary tree with next pointer.
	public class TreeLinkNode {
		int val;
		TreeLinkNode left, right, next;

		TreeLinkNode(int x) {
			val = x;
		}
	}

좋은 웹페이지 즐겨찾기