[LeetCode]104.Maximum Depth of Binary Tree

【题目】

【代码】

【递归】

时间复杂度为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
*   来源：http://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;
}