力ボタンLeetCode【毎日1題】——543.ツリーの直径(Python 3)深さ優先探索(DFS)

難易度:簡単
タイプ:ツリー、深度優先検索(Depth-First-Search,DFS)
深さ優先探索は広さ優先探索とは異なり,ツリーの謙虚な遍歴に類似し,再帰的な方法を用いて問題を解決する.
ツリーベースを参照https://www.jianshu.com/p/bf73c8d50dc2
記録:前、中、後序遍歴はいずれも先左後右であり、違いはノードが1、2、3回遍歴されたときに出力されることである.階層遍歴はその名の通り意味がある.
全体的な遍歴の結果、前の順序は、ルートノード--左サブツリー--右サブツリー;中序遍歴は:左サブツリー-ルートノード-右サブツリー;次の順序は、左サブツリー-右サブツリー-ルートノードです.従って,前+中,後+中はいずれも還元二叉木構造を推定できることが分かったが,前+後はだめであった.
タイトル:正の整数targetを入力し、targetの連続正の整数シーケンス(少なくとも2つの数を含む)をすべて出力します.シーケンス内の数字は小さいから大きいまで並べられ、異なるシーケンスは最初の数字に従って小さいから大きいまで並べられます.
例:

          1
         / \
        2   3
       / \     
      4   5 

3を返します.その長さはパス[4,2,1,3]または[5,2,1,3]です.
注:2つのノード間のパスの長さは、それらの間のエッジの数で表されます.
コードコメント:最初の6行のコメントはleetcodeがテスト例のツリー構造を作成したことを注意しています.TreeNodeタイプのオブジェクトにはvol、left、rightの3つのパラメータがあります.現在のノードの値、左サブツリー、右サブツリーを表します.二叉木の直径を解くコードを書くだけでいいです.
問題の解決:
  1. 直径対応経路がルートノードを通過するとは限らない
  2. ルートノードで区切られ、そのノードを通る最長パスのノード数は、左サブツリーの深さ+右サブツリーの深さ+1です.パス長は、まとめ点数-1です.

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

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1
        def depth(root):
            if not root: return 0
            l = depth(root.left)
            r = depth(root.right)
            self.ans = max(l + r + 1, self.ans)
            return max(l, r) + 1
        depth(root)
        return self.ans - 1

時間複雑度:O(N)
空間複雑度:O(Depth)
コミット時間
結果の送信
実行時間
メモリ消費量
言語
数秒前
に合格
76 ms
15.6 MB
Python3
タイトルソース:力ボタンリンク:https://leetcode-cn.com/problems/diameter-of-binary-tree