LeetCode-543. 二叉树的直径【树 深度优先搜索 二叉树】
- 题目描述:
- 解题思路一:DFS
- 解题思路二:另一种写法DFS
- 解题思路三:0
题目描述:
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1:
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
输入:root = [1,2]
输出:1
提示:
树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100
解题思路一:DFS
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(node):
if not node:
return -1 # 下面 +1 后,对于叶子节点就刚好是 0
l_ren = dfs(node.left) + 1 # 左子树最大链长+1
r_ren = dfs(node.right) + 1 # 右子树最大链长+1
nonlocal ans
ans = max(l_ren + r_ren, ans) # 两条链拼成路径
return max(l_ren, r_ren) # 当前子树最大链长
dfs(root)
return ans
时间复杂度:O(n)
空间复杂度:O(n)
解题思路二:另一种写法DFS
# 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 __init__(self):
self.max = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.depth(root)
return self.max
def depth(self, root):
if not root:
return 0
l = self.depth(root.left)
r = self.depth(root.right)
'''每个结点都要去判断左子树+右子树的高度是否大于self.max,更新最大值'''
self.max = max(self.max, l+r)
# 返回的是高度
return max(l, r) + 1
时间复杂度:O(n)
空间复杂度:O(n)
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)