428
[LeetCode]104.Maximum Depth of Binary Tree
【題目】
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
【代碼】
【遞歸】
時間複雜度為O(n) 空間複雜度為O（logn）
/**
* Definition for binary tree
* 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 left = maxDepth(root->left);
int right = maxDepth(root->right);
return 1 + max(left,right);
}
};
【隊列】
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//二叉樹最大深度（層次遍曆，遍曆一層高度加1）
int maxDepth(TreeNode *root) {
int height = 0,rowCount = 1;
if(root == NULL){
return 0;
}
//創建隊列
queue<TreeNode*> queue;
//添加根節點
queue.push(root);
//層次遍曆
while(!queue.empty()){
//隊列頭元素
TreeNode *node = queue.front();
//出隊列
queue.pop();
//一層的元素個數減1，一層遍曆完高度加1
rowCount --;
if(node->left){
queue.push(node->left);
}
if(node->right){
queue.push(node->right);
}
//一層遍曆完
if(rowCount == 0){
//高度加1
height++;
//下一層元素個數
rowCount = queue.size();
}
}
return height;
}
};
【棧】
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
stack<TreeNode*> S;
int maxDepth = 0;
TreeNode *prev = NULL;
S.push(root);
while (!S.empty()) {
TreeNode *curr = S.top();
if (prev == NULL || prev->left == curr || prev->right == curr) {
if (curr->left)
S.push(curr->left);
else if (curr->right)
S.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
S.push(curr->right);
} else {
S.pop();
}
prev = curr;
if (S.size() > maxDepth)
maxDepth = S.size();
}
return maxDepth;
}
};
【測試】
/*********************************
* 日期：2013-12-08
* 作者：SJF0115
* 題目: 104.Maximum Depth of Binary Tree
* 來源：https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <malloc.h>
#include <stdio.h>
using namespace std;
typedef struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}TreeNode,*BiTree;
//按先序序列創建二叉樹
int CreateBiTree(BiTree &T){
int data;
//按先序次序輸入二叉樹中結點的值，‘-1’表示空樹
scanf("%d",&data);
if(data == -1){
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(TreeNode));
//生成根結點
T->val = data;
//構造左子樹
CreateBiTree(T->left);
//構造右子樹
CreateBiTree(T->right);
}
return 0;
}
//二叉樹最大深度（遞歸）
int maxDepth(TreeNode *root) {
if(root == NULL){
return 0;
}
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return 1 + max(left,right);
}
int main() {
int i,n;
BiTree T = NULL;
CreateBiTree(T);
printf("%d\n",maxDepth(T));
return 0;
}
最後更新：2017-04-03 12:53:42