Binary Treeの構造について

Leetcodeにて問題を解いているのですが
もしよろければコードの意味を
教えていただけますと助かります。

下記の問題を解いています。（言語はPythonです）

答えは

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
            if root is None:
                return 0
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

なのですが
(参考資料)

ちょっとコードの意味が分からないでおります。。
以下質問です。

質問１，

root = [3,9,20,null,null,15,7]

を図にすると、

           3
        /      \
      9         20
    / \        /  \
null null    15    7

になると予測しているのですが
これは正しいのでしょうか？正しいとするなら、

 [3,9,20,null,null,15,7]

のリストがなぜこのようなツリー構造として認識されるのかがよくわかりません。
これはそういうものと理解するしかないのでしょうか？

質問２，
right, leftとはなんでしょうか？
こちらはコードに定義されているっぽい記載があるのですが

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

Printして中身を見てみたのですが

            print(root.left)
            print(root.right)

よくわからない結果が返ってきました。

TreeNode{val: 9, left: None, right: None}
TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}
None
None
TreeNode{val: 15, left: None, right: None}
TreeNode{val: 7, left: None, right: None}
None
None
None
None

このような結果が返ってくる原理がよくわかりません。。

行動規範の内容に同意します

回答2件

質問１

通常であれば、以下のように木を明示的に作るのが普通です。

python
1root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

おそらく、リストから木を作成するコードの存在を前提としているのだと思われます。
この回答の末尾のコードにあるmakeのような関数があるという前提なのでしょう。

質問２

left、rightは、TreeNodeクラスのインスタンスのデータ属性です。
上記のようにrootを定義した場合、root.leftはTreeNode(9)で、root.rightはTreeNode(20, TreeNode(15), TreeNode(7))になります。
理解できないようであれば、「クラス」について調べてみることをお勧めします。

あと、元のコードを理解するためには、「再帰呼び出し」についての知識が必要です。
こちらも調べてみることをお勧めします。

念のため、実行経路が分かりやすいように、インデント付きでログを出力するようにしたmaxDepthを貼っておきます。
ローカルで動作を確認できるように、必要なコードをいくつか追加してあります。

python
1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6    def __repr__(self):
7        if self.right is not None:
8            return f'TreeNode({self.val!r}, {self.left!r}, {self.right!r})'
9        elif self.left is not None:
10            return f'TreeNode({self.val!r}, {self.left!r})'
11        else:
12            return f'TreeNode({self.val!r})'
13
14def make(l, i = 0):
15    if 0 <= i < len(l) and l[i] is not None:
16        return TreeNode(l[i], make(l, i * 2 + 1), make(l, i * 2 + 2))
17    return None
18
19def dprint(i, v):
20    print(' ' * (i * 4), end='')
21    print(v)
22
23class Solution:
24    def maxDepth(self, root: TreeNode, i = 0) -> int:
25        dprint(i, f'maxDepth({root})')
26        if root is None:
27            dprint(i, 'return 0')
28            return 0
29        dprint(i, f'l = self.maxDepth({root.left})')
30        l = self.maxDepth(root.left, i + 1)
31        dprint(i, f'l = {l}')
32        dprint(i, f'r = self.maxDepth({root.right})')
33        r = self.maxDepth(root.right, i + 1)
34        dprint(i, f'r = {r}')
35        dprint(i, f'return max({l}, {r}) + 1')
36        return max(l, r) + 1
37
38root = make([3, 9, 20, None, None, 15, 7])
39print(Solution().maxDepth(root))

実行結果は、以下の通りです。

text
1maxDepth(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))))
2l = self.maxDepth(TreeNode(9))
3    maxDepth(TreeNode(9))
4    l = self.maxDepth(None)
5        maxDepth(None)
6        return 0
7    l = 0
8    r = self.maxDepth(None)
9        maxDepth(None)
10        return 0
11    r = 0
12    return max(0, 0) + 1
13l = 1
14r = self.maxDepth(TreeNode(20, TreeNode(15), TreeNode(7)))
15    maxDepth(TreeNode(20, TreeNode(15), TreeNode(7)))
16    l = self.maxDepth(TreeNode(15))
17        maxDepth(TreeNode(15))
18        l = self.maxDepth(None)
19            maxDepth(None)
20            return 0
21        l = 0
22        r = self.maxDepth(None)
23            maxDepth(None)
24            return 0
25        r = 0
26        return max(0, 0) + 1
27    l = 1
28    r = self.maxDepth(TreeNode(7))
29        maxDepth(TreeNode(7))
30        l = self.maxDepth(None)
31            maxDepth(None)
32            return 0
33        l = 0
34        r = self.maxDepth(None)
35            maxDepth(None)
36            return 0
37        r = 0
38        return max(0, 0) + 1
39    r = 1
40    return max(1, 1) + 1
41r = 2
42return max(1, 2) + 1
433

投稿2021/10/08 15:08

actorbug

総合スコア2224

ベストアンサー

予測しているのですがこれは正しいのでしょうか？

Noneは書かないようですが、それでよいのではないでしょうか。

なぜこのようなツリー構造として認識されるのかがよくわかりません。

一般的には認識されません。
Leetcodeというサイト内での約束事なのでしょう。
おそらく、Introduction to Data Structure Binary Treeからちゃんとやればわかるようになっているのだと思います。

right, leftとはなんでしょうか？

右の枝と左の枝です。
枝が二本あるからbinary(ふたつの)tree(木)ですね。

よくわからない結果が返ってきました。

python
1# class TreeNode:
2#     def __init__(self, val=0, left=None, right=None):
3#         self.val = val
4#         self.left = left
5#         self.right = right
6
7
8には書かれていませんが、__repr__が定義されているのでしょう。

これが良くわからないなら、Leetcodeをやる前にPythonの基礎をしっかりやることをお勧めします。

投稿2021/10/05 09:52

ppaul

総合スコア24666

Tomato_leaf

2021/10/06 05:35

ありがとうございます。 (root.left)と(root.right)の中身は辞書型でその中に辞書が内包されていると構造かと思うのですが正しいでしょうか？そして print(self.maxDepth(root.left)) print(self.maxDepth(root.right)) と書いてみると下記のような結果がプリントされたんですが --------- --------- 0 0 1 --------- --------- 0 0 1 --------- 0 0 1 --------- 0 0 --------- 0 0 2 --------- 0 0 --------- --------- 0 0 1 --------- 0 0 1 --------- 0 0 --------- 0 0 この数字は --------- TreeNode{val: 9, left: None, right: None} TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}} --------- None None --------- TreeNode{val: 15, left: None, right: None} TreeNode{val: 7, left: None, right: None} --------- None None --------- None None の何を数えているのでしょうか？

ppaul

2021/10/10 14:58

(root.left)と(root.right)の中身は辞書型でその中に辞書が内包されていると構造かと思うのですが正しいでしょうか？違います。どちらもTreeNodeのインスタンスかあるいはNoneです。この数字は何を数えているのでしょうか？それも、Introduction to Data Structure Binary Treeからちゃんとやればわかるようになっているのだと思います。途中を飛ばして最後だけ見るのではなく、最初から順を追って理解していくことをお勧めします。

Tomato_leaf

2021/10/21 04:04

ありがとうございます。ようやくりかいできました。

行動規範の内容に同意します

あなたの回答