116. 填充每个节点的下一个右侧节点指针

题目:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

代码:

class Solution {

    public Node connect(Node root) {
        if (root != null) {
            if (root.left != null) {
                //左子节点的next
                root.left.next = root.right;
                //递归左子节点
                this.connect(root.left);
            }
            if (root.right != null) {
                //右子节点的next
                if (root.next != null) {
                    root.right.next = root.next.left;
                }
                //递归右子节点
                this.connect(root.right);
            }
        }
        return root;
    }

}

题目要求只能使用常量级额外空间。也就是说不能使用变量,那么我们就考虑是用递归来实现。

将题目简化,其实就是要给每个节点的next属性赋值,值为同一层级往右的下一个节点。因为我们使用的是递归的方法,所以对于入参root有如下:

1、root为根节点,所以root没有兄弟节点,则root.next=null,又因为对象的属性默认值为null,所以这种情况我们不处理。

2、root为非根节点,所以root有兄弟节点,则root.next可能有值,这个值取决于它的父节点,但是单从入参我们无法获取父节点,所以我们就将这种情况放在进入递归前的父节点那一层处理。

3、由于2的存在,所以我们在递归root的左右节点时,需要先处理root的左右节点的next的值,左右子节点分情况处理。

4、左子节点,root.left.next=root.right,不用多说。

5、右子节点,情况比较复杂,因为它的next取决于父节点的兄弟节点的子节点,虽然比较绕口,但是由于4的操作在前,所以递归的时候,父节点的next值已经做了处理,所以右子节点root.right.next=root.next.left。

6、综上我们通过递归即可对所有的节点的next属性进行处理,需要注意的是要有非空判断,防止出现空指针异常。

如图所示,图中红色箭头是代码中红色部分建立的联系,即亲兄弟。图中绿色箭头是代码中绿色部分建立的联系,即堂兄弟。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏