利用层次遍历非递归求二叉树高度

╰半橙微兮° 2022-07-16 03:19 116阅读 0赞

leetcode 104. 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;
        }
    };

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

[leetcode 111. 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;
        }
    };

[leetcode 111. Minimum Depth of Binary Tree]: https://leetcode.com/problems/minimum-depth-of-binary-tree/