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

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

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

/** 

 * 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.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.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; 

 } 

};

原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/15247.html