剑指offer——二叉树的深度

题目描述：
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路1：按照深度优先遍历，设置一个全局变量max_depth用于记录树的最大深度，遍历整棵二叉树的所有节点，到达叶子节点则判断一下是否比max_depth更大，是则更新最大深度

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr)
            return 0;
        DFS(pRoot,0);
        return max_depth;
    }
    void DFS(TreeNode* root,int depth){
        if(root==nullptr)
            return ;
        depth+=1;
        if(root->left==nullptr&&root->right==nullptr){
            if(depth>max_depth)
                max_depth=depth;
            return ;
        }
        DFS(root->left,depth);
        DFS(root->right,depth);
    }
private:
    int max_depth=0;
};

思路2：按照广度优先遍历，每遍历一层，max_depth+1

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr)
            return 0;
        queue<TreeNode*> que;
        que.push(pRoot);
        while(!que.empty()){
            int size=que.size();
            max_depth++;
            while(size--){
                TreeNode *temp=que.front();
                que.pop();
                if(temp->left)
                    que.push(temp->left);
                if(temp->right)
                    que.push(temp->right);
            }
        }
        return max_depth;
    }
private:
    int max_depth=0;
};

思路3：树的高度是左右子树中较大的那个高度+1

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot==nullptr)
            return 0;
        int depth=getHigh(pRoot);
        return depth;
    }
    int getHigh(TreeNode* pRoot){
        if(pRoot==nullptr)
            return 0;
        int left=getHigh(pRoot->left);
        int right=getHigh(pRoot->right);
        return max(left,right)+1;
    }
};