二叉树最大深度

1，递归

#include<iostream>
using namespace std;
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 maxDepth(TreeNode* root) 
    {
        if (root == NULL)
            return 0;//说明为叶子节点，深度为0
        int lheight = maxDepth(root->left);//获取左子树最大深度
        int rheight = maxDepth(root->right);//获取右子树最大深度
        return lheight>rheight?lheight+1:rheight+1;
    }
};
void test()
{
    TreeNode t1 = { 3,NULL,NULL };
    TreeNode t2 = { 9,NULL,NULL };
    TreeNode t3 = { 20,NULL,NULL };
    TreeNode t4 = { 15,NULL,NULL };
    TreeNode t5 = { 7,NULL,NULL };
    t1.left = &t2;
    t1.right = &t3;
    t3.left = &t4;
    t3.right = &t5;
    Solution s;
    int ret=s.maxDepth(&t1);
    cout << "最大深度：" << ret << endl;
}
int main()
{
    test();
    system("pause");
    return 0;
}

简化版递归：

  int maxDepth(TreeNode* root) 
    {
        //如果root==NULL满足就返回0,表示是叶子节点，深度为0
        //否则返回当前节点左右子树中最深的深度
        return root==NULL ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

BFS—深度优先遍历—类似层序遍历

思路：每一次把当前层的节点都放入队列中，记录当前层上存在几个节点，然后再次进行循环，把队列中的元素挨个出队，每有一个元素出队，就判断他有没有左右子树，如果有就把左右子树的节点放入队列中，队列中元素出队个数就是记录当前层数上的节点个数。没当一层上的节点都出队完，就相当于此树存在一层，用一个变量记录层数。

    int maxDepth(TreeNode* root) 
    {
        if (root == NULL)
            return 0;
        deque<TreeNode*> queue;
        queue.push_back(root);
        int count = 0;//计算当前层数
        while (!queue.empty())
        {
            int size = queue.size();//计算当前层节点个数
            while (size-- > 0)//队列中还存在元素
            {
                //先获取当前队列中第一个节点
                TreeNode* node = queue.front();
                //当前队列中第一个节点出队
                queue.pop_front();
                //将当前节点的左右子树加入队列
                if (node->left)
                {
                    queue.push_back(node->left);
                }
                if (node->right)
                {
                    queue.push_back(node->right);
                }
            }
            count++;//当前层元素出队完毕，下一层元素已经全部加入队列中，层数加一
        }
        return count;
    }

DFS—深度优先遍历—类似前序遍历

就是法1的递归算法