首页 > 代码库 > LeetCode 117 Populating Next Right Pointers in Each Node II

LeetCode 117 Populating Next Right Pointers in Each Node II

2024-07-30 08:39:54   222人阅读

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
Anwser 1：
	public void connect(TreeLinkNode root) {
		if (null == root) {
			return;
		}

		TreeLinkNode cur = root.next;
		TreeLinkNode p = null;

		while (cur != null) { // find last right node (left or right)
			if (cur.left != null) {
				p = cur.left;
				break;
			}
			if (cur.right != null) {
				p = cur.right;
				break;
			}
			cur = cur.next;
		}

		if (root.right != null) {
			root.right.next = p;
		}

		if (root.left != null) {
			root.left.next = root.right != null ? root.right : p;
		}

		connect(root.right); // from right to left
		connect(root.left);
	}


注意点： 
1） list为非完美二叉树，右分支可能为空，因此从right -> left 遍历 
2） 从最右分支开始查找，且root没有 left 节点，则找 right 节点 
Anwser 2：
	public void connect(TreeLinkNode root) {
		if (null == root) {
			return;
		}

		LinkedList<TreeLinkNode> Q = new LinkedList<TreeLinkNode>(); // save one
																		// line
																		// root(s)
		LinkedList<TreeLinkNode> Q2 = new LinkedList<TreeLinkNode>();
		; // save next one line root(s), swap with Q
		Q.push(root);

		while (!Q.isEmpty()) {
			TreeLinkNode tmp = Q.getFirst();
			Q.pop();

			if (tmp.left != null)
				Q2.add(tmp.left);
			if (tmp.right != null)
				Q2.add(tmp.right);

			if (Q.isEmpty()) {
				tmp.next = null;
				LinkedList<TreeLinkNode> tmpQ = Q; // swap queue
				Q = Q2;
				Q2 = tmpQ;
			} else {
				tmp.next = Q.getFirst();
			}
		}
	}
注意点： 
1） 新增一个Q2队列，保存下一行的全部元素，辅助判断是最后一个元素（Q为空）则置为NULL 
2） queue队列实现比递归要好 
Anwser 3：
	public void connect(TreeLinkNode root) {
		LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
		if (root == null)
			return;
		TreeLinkNode p;
		queue.add(root);
		queue.add(null);// flag

		while (!queue.isEmpty()) {
			p = queue.pop();
			if (p != null) {
				if (p.left != null) {
					queue.add(p.left);
				}
				if (p.right != null) {
					queue.add(p.right);
				}
				p.next = queue.getFirst();
			} else {
				if (queue.isEmpty()) {
					return;
				}
				queue.add(null);
			}
		}
	}



LeetCode 117 Populating Next Right Pointers in Each Node II


联系
我们