LeetCode - Populating Next Right Pointers in Each Node II 및 변형 문제

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

첫 번째 문제의 요구는 완전 두 갈래 나무이고, 두 번째 문제는 이 요구가 없다.분명히 공간 복잡도의 요구가 없다면 O(1) 이 문제는 차원별로 두루 훑어보는 사상에 따라 풀 수 있고 도구 방법의 개념을 언급했기 때문에 이 문제를 먼저 볼 수 있다.http://blog.csdn.net/my_jobs/article/details/47665089순서대로 두루 다니다.충분히 이 문제를 개조해서 만들 수 있다.그러나 이 두 문제 모두 공간의 복잡도가 O(1)여야 한다.그래서 이 방법은 안 되지만 코드를 제시할 수 있어 이 두 문제에 대해 완전히 통용된다.

    public void connect(TreeLinkNode root) {
        if (root == null) return;
        LinkedList<TreeLinkNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            TreeLinkNode pre = null;
            for (int i = 0; i < len; i++) {
                TreeLinkNode node = queue.poll();
                if (i == 0) {
                    pre = node;
                } else {
                    pre.next = node;
                    pre = pre.next;
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
    }

이를 통해 알 수 있듯이 위의 코드는 완전히 개조된 것이기 때문에 흔히 볼 수 있는 알고리즘은 틀림없이 마음에 익숙할 것이다.
먼저 첫 번째를 하는 것이 비교적 쉽다.코드를 보면 알 수 있습니다.

    public void connect(TreeLinkNode root) {
        if (root == null) return;
        root.next = null;
        while (root.left != null) {
            TreeLinkNode p = root;
            while (p != null) {
                p.left.next = p.right;
                if (p.next != null) {
                    p.right.next = p.next.left;
                } else {
                    p.right.next = null;
                }
                p = p.next;
            }
            root = root.next;
        }
    }

이 정수는 단계가 교체될 때 이미 구축된 것, 예를 들어next바늘을 효과적으로 이용해야 한다는 것이다.
두 번째 문제를 보고 있으면 두 번째 문제는 어려워진다.

    public void connect(TreeLinkNode root) {
        while(root != null){
            TreeLinkNode childHead = new TreeLinkNode(0);
            TreeLinkNode p = childHead;
            while (root != null){
                if (root.left != null) { 
                    p.next = root.left; 
                    p = p.next;
                }
                if (root.right != null) { 
                    p.next = root.right; 
                    p = p.next;
                }
                root = root.next;
            }
            p.next = null;
            root = childHead.next;
        }
    }

이 문제는 각 층의 헤드 바늘을 비교하는데 너무 교묘하다.체인 시계의 성질을 이용했다!!!
개조 문제:
Given the following binary tree,

         1
       /  \
      2    3
       \  / \
       5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /   
      2 -> 3 -> NULL
     /       
    5->6->7 -> NULL

트리의 데이터 구조는 변하지 않습니다. 현재 노드가 이 층의 첫 번째 노드라면, 왼쪽 바늘은 아래층의 첫 번째 노드를 가리키고, 그렇지 않으면 비어 있습니다.right 포인터는 이 층의 다음 노드를 가리킨다.만능의 해법, 차원 반복:

    public TreeNode treeToList(TreeNode root) {
    	if (root == null) return null;
    	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.add(root);
    	TreeNode head = new TreeNode(0);
    	while (!queue.isEmpty()) {
    		int len = queue.size();
    		TreeNode pre = null;
    		for (int i = 0; i < len; i++) {
    			TreeNode node = queue.poll();
    			if (node.left != null) queue.add(node.left);
    			if (node.right != null) queue.add(node.right);
    			node.left = null;
    			node.right = null;
    			if (i == 0) {
    				pre = node;
    				head.left = pre;
    				head = head.left;
    			} else {
    				pre.right = node;
    				pre = pre.right;
    			}
    		}
    	}
    	return root;
    }

위의 두 문제에 비해next바늘을 이용할 수 있습니다. 이것이 있는지 없는지는 반드시 본 하층의 노드를 모두 보존해야만 본 층의 노드 관계를 수정할 수 있습니다!!!