二叉树的最大深度

题目：

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思想1：

使用后序遍历分别求根节点的左子树的高度l和右子树的高度r，最大深度就是根节点的高度为max(l,r) + 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int GetHeight(TreeNode* node)
    {
        if(node == NULL)
        {
            return 0;
        }
        int left_height = GetHeight(node->left);
        int right_height = GetHeight(node->right);
        return max(left_height, right_height) + 1;
    }
    int maxDepth(TreeNode* root) {
        return GetHeight(root);
    }
};

思想2：

使用前序遍历分别求根节点到叶子节点的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int result;   //相当于是类中的"全局变量",记录每条路径的最大值
    void GetDeepth(TreeNode* node, int deepth)
    {
        result = deepth > result ? deepth : result;  //和每个阶段的deepth对比，取最大值
        if(NULL == node->left && NULL == node->right)   return;

        if(node->left)
        {
            deepth++;
            GetDeepth(node->left, deepth);
            deepth--;     //回溯，减一
        }
        if(node -> right)
        {
            deepth++;
            GetDeepth(node->right, right_deepth);
            deepth--;     //回溯，减一
        }

    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if(NULL == root)
        {
            return result;
        }
        GetDeepth(root, 1);
        return result;
    }
};

思想3：

通过层次遍历的思想得到最大深度，最后一层就是最大深度。

1.把根节点放入队列中，使用size变量记录当前队列的容量，遍历完该size容量后，深度加一。并在遍历的过程中，把遍历的节点的下一层孩子节点放在队列中。

2.更新size，并继续遍历，直至队列为空。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};