【LeetCode】116#填充同一层的兄弟节点

题目描述

给定一个二叉树

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

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

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

说明:

• 你只能使用额外常数空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
• 你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例:

给定完美二叉树，

     1
   /  
  2    3
 /   / 
4  5  6  7

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

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

---

解题思路

递归法

以一棵只包含三个节点的完美二叉树为最小单位，后面就简称最小树。

在一棵最小树里，可以直接左子节点指向右子节点就可以了，但是二叉树的层数增多后，两棵最小树之间的兄弟节点就不太好找到了。

比如题目中给出的二叉树，2->3，4->5，6->7都比较好添加，就是在同一棵最小树里面的左子节点指向右子节点，对原二叉树进行根节点的遍历，然后在每次遍历进行一次指向操作就可以了。但是类似于5->6这种两棵最小树之间的指向就不太容易处理了。

我们可以使用两个指针表示当前正在处理的左子节点和右子节点（不一定在同一棵最小树中），每次遍历，处理完同一棵最小树的左子节点指向右子节点后，将两个指针「下沉」，再执行一次指向操作，直到最底层。

源代码

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        TreeLinkNode left = root.left;
        TreeLinkNode right = root.right;
        connect(left);
        connect(right);
        while(left != null && right != null){
            left.next = right;
            left = left.right; // 左指针下沉
            right = right.left; // 右指针下沉
        }
    }
}

心得体会

在本题中，递归处理的套路为：

1. 最小情况
2. 对左子树和右子树调用相应的递归函数处理
3. 具体的处理过程