如何在每个级别上连接二叉树左右分支的最内部节点

Question

考虑下面的树。需要一种算法来在每个级别上连接树的左右分支的最内层节点。从某种意义上说，连接是2->链接是节点3，而3->链接是节点2

输入树

          1
        /  \
       2     3 
      / \    / \
     4   5  6   7
    /   /      /
   8   9      10 
      / \    / \
     11 12  13  14

输出树

         1
        /  \
       2=====3 
      / \    / \
     4   5==6   7
    /   /      /
   8   9======10 
      / \    / \
     11 12==13  14

Answer 1

您的级别顺序遍历想法很不错。想象一下，彼此独立地对根的左子树和右子树进行级别顺序遍历。然后，

• 您在扫描左子树时在每个级别访问的最后一个节点是左子树中每个层的最右节点，并且
• 您在扫描右子树时在每个级别访问的第一个节点是右子树中每个层的最左节点。

然后您可以记下这些节点并将它们连接在一起以获得总体结果。

希望这会有所帮助！