利用层次遍历非递归求二叉树高度详解编程语言

Maximum Depth of Binary Tree

求二叉树的最大深度，也即其高度。

递归版本比较容易理解。利用层次遍历非递归求二叉树高度主要的思想是：一层一层地出队列 — 在我们每次访问完毕一层时，这时队列中存储的刚好是下一层的所有元素。所以在下一次循环开始时，首先记录该层的元素个数，一次性访问完这一层的所有元素。

/** 
 * 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 maxDepth(TreeNode* root) { 
      //return maxDepthWithLevelTraversal(root); 
      return maxDepthRecursion(root); 
    } 
 /* 递归版本 */ 
 int maxDepthRecursion(TreeNode* root){ 
       int HL, HR, MaxH; 
       if (root){ 
           HL = maxDepth(root->left); 
           HR = maxDepth(root->right); 
           MaxH = (HL > HR) ? HL : HR; 
           return MaxH + 1; 
       } 
       else  
           return 0; 
    } 
 /* 层次遍历的非递归版本 */ 
 int maxDepthWithLevelTraversal(TreeNode* root){
  /* 判断树是否为空 */ 
  if(!root){
       return 0; 
    } 
     int height = 0;    // 初始化树的高度为0 
     queue<TreeNode*>Q;  // 初始化一个队列，并将根节点入队 
        Q.push(root); 
     /* 当队列不为空时 */ 
     /* 实际上当每次循环开始时，队列中存储的刚好是将要访问下一层的所有元素*/ 
     while(!Q.empty()){ 
            height++; int curLevelSize = Q.size();  
            // 记录当前层元素个数 
            int cnt = 0; 
            /* 弹出当前层所有元素 */ 
            while(cnt < curLevelSize){ 
                TreeNode* temp = Q.front(); 
                Q.pop(); 
                cnt++; 
                /* 将下一层的元素入队列 */ 
                if(temp->left){ 
                    Q.push(temp->left); 
                } if(temp->right){ 
                    Q.push(temp->right); 
                } 
            } 
        } return height; 
    } 
};

继续思考上面的非递归代码还用来做什么？比如求树的宽度，也就是元素个数最多的那一层元素个数。记录所有层间的最大值即可。

Minimum Depth of Binary Tree
这题是求二叉树的最小高度，与最大高度类似，不同之处在于层次遍历时，如果在该层遇到有叶子节点则立即返回，在进行层次遍历时需要进行叶子节点的判断。

/** 
 * 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 minDepth(TreeNode* root) { if(!root) 
            return 0; 
 
        queue<TreeNode*>Q; 
        Q.push(root); 
     int height = 0; 
     while(!Q.empty()){ 
            height++; 
     int curLevelSize = Q.size(); int cnt = 0; 
     while(cnt++ < curLevelSize){ 
                TreeNode *temp = Q.front(); 
                Q.pop(); 
                /* 此处比二叉树高度多了叶子节点的判断 */ 
                if(!temp->left && !temp->right) 
                    return height; 
                if(temp->left) 
                    Q.push(temp->left); if(temp->right) 
                    Q.push(temp->right); 
            } 
        } 
        return height; 
    } 
};