跟着姚桑学算法-二叉树的深度

题. 二叉树的深度

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

数据范围
树中节点数量 [0,500]。

样例

输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
    8
   / \
  12  2
     / \
    6   4

输出：3

【题解】--- DFS、BFS

二叉树（Binary tree） 是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

__二叉树是n个有限元素的集合__，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。

关于二叉树的性质：

• 性质1：二叉树的第i层上至多有2i-1（i≥1）个节点 。
• 性质2：深度为h的二叉树中至多含有2h-1个节点 。
• 性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1 。
• 性质4：具有n个节点的满二叉树深为log2n+1。
• 性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点 。
当i>1时，该节点的双亲节点的编号为i/2 。
若2i≤n，则有编号为2i的左节点，否则没有左节点 。
若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。

对于本题： 有两种方法。
方法1：利用dfs记录当前层，遇到叶子更新全局最大层数。

方法2：利用bfs 每次都把上一层弹出。

简易题，具体解法见代码。

C++代码实现：

class Solution {
public:

    int ans=1;
    int treeDepth(TreeNode* root) {
        if(!root) return 0;
        dfs(root,0);
        return ans; 
    }

    void dfs(TreeNode* r,int lev){
        if(!r){
            ans=max(lev,ans);
            return;
        } 

        dfs(r->left,lev+1);//写成lev++,需要恢复现场
        dfs(r->right,lev+1);
    }
};

// 方法二：
class Solution {
public:

    int treeDepth(TreeNode* root){
        if(!root) return 0;


        queue<TreeNode*> q;
        q.push(root);

        int lev=0;

        while(!q.empty()){
            TreeNode* tail=q.back(),*head;//记录上一层的末尾

            while(!q.empty()){
                head=q.front();q.pop();
                if(head->left) q.push(head->left);
                if(head->right) q.push(head->right);

                if(head==tail) break;//此时上一层都已经出队
            }

            lev++;

        }

        return lev;
    }
};