在之前的博客中，博主给出了对于层序遍历算法的核心思想的分析。而层序遍历这样一种从左至右，一层一层访问的思想，与求解二叉树的宽度和高度的思路是十分贴合的，几乎可以直接将层序遍历的算法代码拿过来用。当然，一点必要的修改是需要的。

1. 二叉树的宽度

　　若某一层的节点数不少于其他层次的节点数，那么该节点数即为二叉树的宽度。在访问过程中，我们只需要将同一层中的节点同时入栈即可。为此，我们也只需要知道上一层队列中元素的多少，在将该queue中所有元素出队列的同时，将下一层的元素进队列，完成交接。这样，便可以清晰地知道每一层中节点的多少，自然也知晓树的宽度。

1 int treeWidth(Bitree *root){ 2   if(!root){ 3     return 0; 4   } 5   int width = 0; 6   int maxWidth = 0; 7   queue
     
       Q; 8   Bitree *p = nullptr; 9   Q.push(root);10   while(!Q.empty()){11     width = Q.size();12     if(maxWidth < width){13       maxWidth = width;14     }15     for(int i=0; i
      
       left){19         Q.push(p->left);20       }21       if(p->right){22         Q.push(p->right);23       }24     }25   }26   return maxWidth;27 }
      
     

2. 树的高度

　　在上述算法中，知道了每一层中节点的个数，其实也很容易知道树的高度，简直就是顺便的事。由此，可以给出相应的非递归算法。

1 int treeHeight2(Bitree *root){ 2   if(!root){ 3     return 0; 4   } 5   int height = 0; 6   int width = 0; 7   queue
     
       Q; 8   Bitree *p = nullptr; 9   Q.push(root);10   while(!Q.empty()){11     width = Q.size();12     height++;13     for(int i=0; i
      
       left){17         Q.push(p->left);18       }19       if(p->right){20         Q.push(p->right);21       }22     }23   }24   return height;25 }
      
     

当然，对于树的高度，还有一种代码简洁的递归算法，也一并呈上。

1 int treeHeight1(Bitree *root){2   if(!root){3     return 0;4   }5   int leftHeight = treeHeight1(root->left);6   int rightHeight = treeHeight1(root->right);7   return leftHeight>rightHeight ? leftHeight+1 :rightHeight+1;8 }

递归思想其实很简单，代码也清晰易懂，即左右子树的较高者加上1（root高度为1）即可。树的高度等价于从根节点到叶子节点的最长路径的长度，后续博主也会讨论到其他变体，例如求解从根节点到叶子节点的最短路径长度。