二叉树的深度——C++

剑指offer 55：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

该题可用两种方法，一种是深度优先遍历（递归），一种是广度优先遍历（非递归）

 int maxDepth1(TreeNode* root) {                //递归
        if (root==nullptr)
        return 0;
        int LeftDeep = maxDepth(root->left);
        int RightDeep = maxDepth(root->right);
        return max(LeftDeep,RightDeep)+1;
    }

广度优先遍历其实和二叉树的层序遍历的写法是类似的，采用队列的方法。值得注意的是，内层的while结束后，要查看当前的队列中还剩几个元素。

int maxDepth(TreeNode* root) {                //非递归
        
        if(root == nullptr)
        return 0;
               
        queue QNode;
        QNode.push(root);
        int ans=0;

        while(QNode.size())   
        {
            int num = QNode.size();
            while(num > 0)
            {
               TreeNode* QTemp = QNode.front();
               QNode.pop();
               if(QTemp->left)  QNode.push(QTemp->left);
               if(QTemp->right) QNode.push(QTemp->right);
               num--;
           } 
           ans++;
        }
        return ans;
    }