LeetCode 2020-11-13: Populating Next Right Pointers in Each…

LeetCode daily challenge の問題 Populating Next Right Pointers in Each Node (medium) の挑戦メモです。

問題の概要

• 与えられた完全二分木 (すべての内部ノードが二つの子をもち、また葉ノードが同じ深さである二分木) について、下図 (leetcode.com より借用) のように同じ深さのノードを next でつないでいく
  

考え方

• 一見するとキューを使わないとダメかなー、みたいに思うんだけど、じっくりと考えると順番さえ注意すれば単に深さ優先で再帰すればいいだけの問題であることがわかりますね ☺️
• ポイントは二つ
  • 子ノードを再帰でたどる前に、左の子ノードの next が右の子ノードを指すようにする
  • また、自身のノードの next が存在するのであれば、「右の子ノードの next」を「自身の next の左の子ノード」を指すようにする (これも再帰する前にやっておく)
• 実装 → submit → accept 👍
  • Runtime 0ms 達成 👍👍👍

コード

class Solution {
    public Node connect(Node root) {
        connectRecursive(root);
        return root;
    }

    void connectRecursive(Node node) {
        if (node == null || node.left == null) {
            return;
        }

        node.left.next = node.right;
        if (node.next != null) {
            node.right.next = node.next.left;
        }

        connectRecursive(node.left);
        connectRecursive(node.right);
    }
}