算法题:如何连接树中相同层级的节点?

2021年3月21日17:05:27 发表评论 694 次浏览

给定一个二叉树, 连接相同级别的节点。你会得到一个额外的nextRight指针相同。

最初,所有的nexight指针都指向垃圾值。函数应该将这些指针设置为指向每个节点的右侧。

      10                       10 ------> NULL
      / \                       /      \
     3   5       =>     3 ------> 5 --------> NULL
    / \     \               /  \           \
   4   1   2          4 --> 1 -----> 2 -------> NULL

范例1:

Input:
     3
   /  \
  1    2
Output:
3 1 2
1 3 2
Explanation:The connected tree is
        3 ------> NULL
     /    \
    1-----> 2 ------ NULL

范例2:

Input:
      10
    /   \
   20   30
  /  \
 40  60
Output:
10 20 30 40 60
40 20 60 10 30
Explanation:The connected tree is
         10 ----------> NULL
       /     \
     20 ------> 30 -------> NULL
  /    \
 40 ----> 60 ----------> NULL

你的任务:

你不需要接受别人的意见。完成函数connect(),该函数以root作为参数,连接同一级别的节点。打印由驱动程序代码完成。输出的第一行是级别顺序遍历,第二行是顺序遍历

预期时间复杂度:O(N)

预期辅助空间:O(N)

条件限制:

1 ≤ 节点数 ≤ 10^5

0 ≤ 节点数组 ≤ 10^5

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: