(C++/Python)LeetCode 104.ツリーの最大深さ
8092 ワード
タイトルの説明:二叉木を与えて、その最大の深さを見つけます.
ツリーの深さは、ルートノードから最も遠いリーフノードまでの最長パス上のノード数です.
説明:リーフノードとは、サブノードがないノードを指します.
考え方:キューを使用して各層を巡回
コードは次のとおりです:C+:
Python:
ツリーの深さは、ルートノードから最も遠いリーフノードまでの最長パス上のノード数です.
説明:リーフノードとは、サブノードがないノードを指します.
考え方:キューを使用して各層を巡回
コードは次のとおりです:C+:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL) return 0;
int res=0;
queue<TreeNode*>que;
que.push(root);
while(!que.empty()){
int n=que.size();
for(int i=0;i<n;i++){
TreeNode* cur=que.front();
if(cur->left!=NULL)
que.push(cur->left);
if(cur->right!=NULL)
que.push(cur->right);
que.pop();
}
res++;
}
return res;
}
};
Python:
# 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: TreeNode) -> int:
if not root:return 0
res=0
queue=collections.deque()
queue.append(root)
while queue:
res+=1
for i in range(len(queue)):
node=queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res