填充同一层的兄弟节点 II

[louzhedong]

习题

出处 LeetCode 算法第117题

给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

• 你只能使用额外常数空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

给定二叉树，

     1
   /  \
  2    3
 / \    \
4   5    7

调用你的函数后，该二叉树变为：

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

思路

使用一个栈来保存每一层的节点

解答

var connect = function (root) {
  if (!root) return;
  var stack = [root];
  while (stack.length) {
    var length = stack.length;
    for (var i = 0; i < length; i++) {
      var current = stack.shift();
      if (i < length - 1) {
        current.next = stack[0];
      } else {
        current.next = null;
      }
      if (current.left) stack.push(current.left)
      if (current.right) stack.push(current.right)
    }
  }
};