LeetCode Maximum Depth of Binary Tree

1.题目描述

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.

2.解决方案1

class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL){
            return 0;
        }
        deque<TreeNode*> deqNodes;
        deqNodes.push_back(root);
        int depth = 0;
        int alreadyDoneCount = 1;
        while(deqNodes.empty() == false){
            TreeNode* lastNode = deqNodes.back();
            deqNodes.pop_back();
            alreadyDoneCount--;
            if(lastNode->left){
                deqNodes.push_front(lastNode->left);
            }
            if(lastNode->right){
                deqNodes.push_front(lastNode->right);
            }
            if(alreadyDoneCount == 0){
                ++depth;
                alreadyDoneCount = deqNodes.size();
            }
        }
        return depth;
    }
};

思路：采用宽度优先搜索，只有当添加的全处理了，树的深度才增加1，这个是个小技巧。

3.解决方案2

class Solution {
public:
    int maxDepth(TreeNode *root) {
       if(root == NULL ){
		return 0;
	}else if(root != NULL && (root->left == NULL && root->right == NULL)){
        return 1;
	}


	int leftTreeDepth = maxDepth(root->left);
	int rightTreeDepth = maxDepth(root->right);

	int maxDepth = leftTreeDepth > rightTreeDepth ? leftTreeDepth : rightTreeDepth;

	return maxDepth + 1;
    }
};

思路：树的遍历当然可以用递归，但会比较慢。

http://www.waitingfy.com/archives/1586

数据结构 & 算法 | RSS 2.0 |