二叉树的最大深度算法面试题-leetcode学习之旅（3）

标题

Maximum Depth of Binary Tree

描述

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

c++实现方法代码

1.递归实现，时间复杂度为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);
    }
};

2.队列实现

/**
 * 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;
    }

};</treenode*>

3.栈

/**
 * 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;  
    }  
};




</treenode*>

4.测试

**********************************/
#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;
}
</stdio.h></malloc.h></iostream>