【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.

问题陈述：

求二叉树的深度

题目思路：

1. 广度优先遍历：利用STL中的queue（队列）进行广度优先遍历，计算层数
2. 深度优先遍历：递归调用，当前节点的高度=max（左孩子节点高度，右孩子结点高度）+ 1

代码：

/**
 * 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) {//BFS广度优先遍历
        if (NULL == root)
            return 0;
        queue <TreeNode *> que;
        int nCount = 1;
        int nDepth = 0;// 记树中每一层上的元素个数
 
         que.push(root);
         while(!que.empty()) {
             TreeNode *pTemp = que.front();
             que.pop();
             nCount --; 
             if (pTemp->left)
                 que.push(pTemp->left);
             if (pTemp->right)
                 que.push(pTemp->right);
             
             if (nCount == 0) {
                 nDepth ++;
                 nCount = que.size();
             }
         }
     return nDepth;
    }
};

class Solution {//DFS深度优先遍历
public:
    int maxDepth(TreeNode* root) {
       if (!root) return 0;

    int ldepth = maxDepth(root->left);
    int rdepth = maxDepth(root->right);

    return 1 + max(ldepth, rdepth);
    }
};

结果

---

二叉树的各种遍历以及时间复杂度还要看一下算法导论，看了再来总结