描述

这是一篇指针初学者的题解。这里用2种方法。
知识点：二叉树，队列，树的层次遍历， 分治法
难度：一星

题解

题目抽象：给出一颗二叉树，求树的最大深度，也就是从根节点到所有叶子节点中的最大值。

方法一：分治法

分治法简介：求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，然后合并左边，右边的解，从而求得最终解。具体可参考归并排序。
步骤：

1. 求 pro(left, rigth) -> int
2. 先求pro(left, (left+right)/2) -> lval
3. 再求pro((left+right)/2 + 1, right) -> rval
4. merge(lval, rval) -> result

这里以本题为具体例子：
函数是求二叉树的最大深度，我们不必管函数具体是怎么实现的。
所以最终结果为 max( 头结点左子树的最大深度, 头结点右子树的最大深度)+1

1. 求TreeDepth(TreeNode* pRoot)->int
2. 先求 TreeDepth(pRoot->left) ->lval
3. 再求TreeDepth(pRoot->right) ->rval
4. return max(lval, rval) + 1

代码

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        int lval = TreeDepth(pRoot->left);
        int rval = TreeDepth(pRoot->right);
        return max(lval, rval) + 1;

    }
};

时间复杂度：O(n)
空间复杂度：O(n),当退化到链表时

方法二：层次遍历

求最大深度，可用队列。因为要满足先进先出的特性。

1. 初始化：一个队列queue<TreeNode*> q， 将root节点入队列q
2. 如果队列不空，做如下操作：
3. 弹出队列头，保存为node，将node的左右非空孩子加入队列
4. 做2,3步骤，知道队列为空

如果不需要确定当前遍历到了哪一层，模板如下：

void bfs() {
    vis[] = 0;
    queue<int> pq(start_val);

    while (!pq.empty()) {
        int cur = pq.front(); pq.pop();
        for (遍历cur所有的相邻节点nex) {
            if (nex节点有效 && vis[nex]==0){
                vis[nex] = 1;
                pq.push(nex)
            }
        }
    }
}

如果需要确定遍历到哪一层，模板如下；

void bfs() {
    int level = 0;
    vis[] = 0; // or set
    queue<int> pq(original_val);
    while (!pq.empty()) {
        int sz = pq.size();

        while (sz--) {
                int cur = pq.front(); pq.pop();
            for (遍历cur所有的相邻节点nex) {
                if (nex节点有效 && vis[nex] == 0) {
                    vis[nex] = 1;
                    pq.push(nex)
                }
            } // end for
        } // end inner while
        level++;

    } // end outer while
}

所以本题直接套模板即可：

代码如下：

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        queue<TreeNode*> q;
        q.push(pRoot);
        int leve1 = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto node = q.front(); q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            leve1 += 1;
        }
        return level;

    }
};

时间复杂度：O(n),二叉树的每个节点遍历一次
空间复杂度：O(n),最差情况下，树平衡时，队列最多存储n/2个节点。