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

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

代码:

class Solution {

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

    /**
     * 获取node节点的子辈中,仅次于left节点的节点
     *
     * @param node
     * @return
     */
    private Node leftChildNode(Node node, Node left) {
        if (node != null) {
            //按照优先级,左,右,next的左右顺序返回,直到都为null
            if (node.left != null && node.left != left) {
                //因为node节点一定是left节点的父节点或者父节点的兄弟
                //所以是否可以返回node节点的left节点判断依据是是不是等于left
                return node.left;
            } else if (node.right != null) {
                return node.right;
            } else {
                return this.leftChildNode(node.next, left);
            }
        }
        return null;
    }

}

本题是116. 填充每个节点的下一个右侧节点指针的进阶,区别是本题中的树不是完美的二叉树,也就是二叉树的左右子节点可能为null,我们需要针对这种情况进行特殊处理,其他思路跟116的思路一样。

因为节点可能会有空值,所以我们抽了一个leftChildNode方法用于获取node节点的子辈中,小于left节点的节点,具体思路就是使用node节点的next值一直往下找,直到找到有一个有子节点,且按照左右节点的顺序返回最大的节点,也是递归。

另一个需要注意的是,我们在connect方法中的递归执行顺序也需要相应的做调整,因为在leftChildNode方法中,需要使用到next的值,所以我们要保证在connect方法中,next的值是最先建立起来的,之后再递归左右子树。否则会因为next的值还未建立导致出现错误的结果。

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

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