leetcode104-python 두 갈래 나무 최대 깊이
1896 단어 leetcode - 간단leetcode
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree
[3,9,20,null,null,15,7]
, 3
/ \
9 20
/ \
15 7
return its depth = 3.
문제 해결 요점:
1. 하나의 stack을 이용하여 나무에서 흘러나오는 노드를 배치하고 바늘을 설정하여 각 층의 마지막 뒤로 이동하고 층수에 하나를 더한다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = 0
if root == None:
return ans
st = []
st.append(root)
# temp, gp = st[0], st[0]
gp = st[0]
ans += 1
while len(st) != 0:
temp = st[0]
if temp.left != None:
st.append(temp.left)
if temp.right != None:
st.append(temp.right)
if gp == temp:
gp = st[len(st)-1]
if gp != st[0]:
ans += 1
st.pop(0)
return ans
또 하나는 귀속적인 방법으로 코드가 비교적 짧기 때문에 앞에 용기를 하나 더 사용할 생각을 하지 않아도 된다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
else:
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
처음부터 시작하는 LeetCode Day11 「1315. Sum of Nodes with Even-Valued Grandparent」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 그 대책으로서 LeetCode 되는 사이트에서 대책을...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.