题目描述

blablabla

样例

blablabla

算法1

(层序遍历)

设置变量level记录当前结点所在的层数，设置变量last指向当前层最右节点，每次遍历出队的时候与last指针比较，若两者相等，那么层数加1，并让last指向下一层最右节点，直至遍历完成，level的值即为二叉树的高度
blablabla

循环过程中队列中的元素只可能是两层：当前层和下一层节点，last始终指向当前层最右端节点，若当前层节点到了当前层节点的最后一个时，那么加入到队列中的节点就是下一层的最右端节点

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
        if(!root) return 0;
        TreeNode* last=root;
        queue<TreeNode*> q;
        int level=0;
        q.push(root);
        while(q.size()){
            TreeNode* t=q.front();
            q.pop();
            if(t->left) q.push(t->left);   //左孩子入队
            if(t->right) q.push(t->right);  //右孩子入队
            if(t==last){   //处理该层最右节点
                level++;   //层数增1
                last=q.back();   //last指向下一层
            }
        }
        return level;
    }
};