LeetCode题解二叉树（四）：我要打十个？层序遍历变式九道-创新互联

前言：

本篇涉及的题目都与10 二叉树的层序遍历有关，共九道题

创新互联自2013年创立以来，先为古塔等服务建站，古塔等地企业，进行企业商务咨询服务。为古塔企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

107.二叉树的层次遍历II medium
199.二叉树的右视图 medium
637.二叉树的层平均值 easy
429.N叉树的前序遍历 medium
515.在每个树行中找大值 medium
116.填充每个节点的下一个右侧节点指针 medium
117.填充每个节点的下一个右侧节点指针II medium
104.二叉树的大深度 easy
111.二叉树的最小深度 easy

正文 107 二叉树的层序遍历II medium

给定一个二叉树，返回其节点值自底向上的层次遍历。

和上一题相比，只是需要翻转一下最后结果而已，代码如下：

vector>levelOrderBottom(TreeNode* root) {queueque;
        vector>res;
        if (root) que.push(root);
        while (!que.empty()) {int size = que.size();
            vectorvec;
            for (int i = 0; i< size; i++) {TreeNode *temp = que.front();
                que.pop();
                vec.push_back(temp->val);
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            res.push_back(vec);
        }
        reverse(res.begin(), res.end());
        return res;
    }

199 二叉树的右视图 medium

做这道题首先要知道什么叫做二叉树的右视图，理解起来也简单，和初中学三视图的时候没什么两样，如下图所示，站在二叉树的右边，返回右侧能看到的所有值。

此处就要明确，如果当前层最右边有结点，如上图的结点4，将4加入结果就可以了。但如果没有呢？就需要将5加入节点，基于此要做一个判断。

那么怎么判断呢？其实也不难，当我们把每一层都加入队列后，最后一个元素，就是改层最右边的值，也是右视图能看见的值。

其余的和普通的层序遍历没有什么区别，代码如下：

vectorrightSideView(TreeNode* root) {queueque;
    vectorres;
    if (root) que.push(root);
    while (!que.empty()) {int size = que.size();
        for (int i = 0; i< size; i++) {TreeNode *temp = que.front();
            que.pop();
            if (i == (size - 1)) res.push_back(temp->val);
            if (temp->left) que.push(temp->left);
            if (temp->right) que.push(temp->right);
        }
    }
    return res;
}

637 二叉树的层平均值 easy

这，没什么可说的了，就是做一次普通的层序遍历，然后求一下每层的平均值而已。

代码如下：

vectoraverageOfLevels(TreeNode* root) {queueque;
    vectorres;
    if (root) que.push(root);
    while (!que.empty()) {int size = que.size();
        double sum = 0;
        for (int i = 0; iTreeNode *temp = que.front();
            que.pop();
            sum += temp->val;
            if (temp->left) que.push(temp->left);
            if (temp->right) que.push(temp->right);
        }
        res.push_back(sum / size);
    }
    return res;
}

429 N叉树的层序遍历 medium

不同之处在于，遍历子结点的时候，要用循环处理，其余和二叉树的层序遍历没什么区别，代码如下：

vector>levelOrder(Node* root) {queueque;
    vector>res;
    if (root) que.push(root);
    while (!que.empty()) {int size = que.size();
        vectorvec;
        for (int i = 0; i< size; i++) {Node *cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            // 此处为不同之处
            for (int j = 0; j< cur->children.size(); j++) {if (cur->children[j]) que.push(cur->children[j]);
            }
        }
        res.push_back(vec);
    }
    return res;
}

515 在每个树行中找大值 medium

层序遍历，取每一层的大值

vectorlargestValues(TreeNode* root) {queueque;
        if (root != NULL) que.push(root);
        vectorresult;
        while (!que.empty()) {int size = que.size();
            int maxValue = INT_MIN; // 取每一层的大值
            for (int i = 0; i< size; i++) {TreeNode* node = que.front();
                que.pop();
                maxValue = node->val >maxValue ? node->val : maxValue;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(maxValue); // 把大值放进数组
        }
        return result;
    }

116 填充每个节点的下一个右侧结点指针 medium

（这道题的题目给我一种日式轻小说的错觉

首先要明白题意，在这道题下，每个节点有一个next指针，需要让该指针指向右侧的结点，如下图所示：

116.填充每个节点的下一个右侧节点指针

本质还是层序遍历，但需要用每一层的第一个节点，并且记录上一个结点，令其指向当前结点，代码如下：

Node* connect(Node* root) {queueque;
        if (root) que.push(root);
        while (!que.empty()) {int size = que.size();
            for (int i = 0; i< size; i++) {Node* node = que.front();
                que.pop();
                // 如果不是本层的最后一个
                if (i != size -1) {// 当前结点指向本层的下一个结点
                    node->next = que.front();
                } else 
                    node->next = NULL;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }

其实这道题，如果用递归来做，会简洁很多，LeetCode官方版代码如下：

private:
    void traversal(Node* cur) {if (cur == NULL) return;
                                // 中
        if (cur->left) cur->left->next = cur->right; // 操作1
        if (cur->right) {if (cur->next) cur->right->next = cur->next->left; // 操作2
            else cur->right->next = NULL;
        }
        traversal(cur->left);   // 左
        traversal(cur->right);  // 右
    }
public:
    Node* connect(Node* root) {traversal(root);
        return root;
    }

117 填充每个节点下一个右侧节点指针II medium

和116的区别在于，这道题说的不是完全二叉树了，官方示例见下图：

但是思想还是一致的，我们直接用116的题解，就可以通过（LeetCode你有些偷懒啊）

代码如下，还是放一遍吧：

Node* connect(Node* root) {queueque;
        if (root) que.push(root);
        while (!que.empty()) {int size = que.size();
            for (int i = 0; i< size; i++) {Node* node = que.front();
                que.pop();
                // 如果不是本层的最后一个
                if (i != size -1) {// 当前结点指向本层的下一个结点
                    node->next = que.front();
                } else 
                    node->next = NULL;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }

104 二叉树的大深度 easy

本质还是层序遍历，记录一共遍历了多少层就行，代码如下：

int maxDepth(TreeNode* root) {if (!root) return 0;
    int depth = 0;
    queueque;
    que.push(root);
    while (!que.empty()) {int size = que.size();
        for (int i = 0; i< size; i++) {TreeNode *node = que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        depth++;
    }
    return depth;
}

111 二叉树的最小深度 easy

还是层序遍历，但是要注意一点，如果某个结点的左右子树都为空，就说明已经达到最小深度的那一层了，多了一个判断，代码如下：

int minDepth(TreeNode* root) {if (root == NULL) return 0;
    int depth = 0;
    queueque;
    que.push(root);
    while(!que.empty()) {int size = que.size();
        depth++; // 记录最小深度
        for (int i = 0; i< size; i++) {TreeNode* node = que.front();
            que.pop();
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
            if (!node->left && !node->right) {return depth;
            }
        }
    }
    return depth;
}

这道题也可以用递归来做，代码如下：

int minDepth(TreeNode* root) {if (root == NULL) return 0;
    if (root->left == NULL && root->right != NULL) {return 1 + minDepth(root->right);
    }
    if (root->left != NULL && root->right == NULL) {return 1 + minDepth(root->left);
    }
    // 相当于左右子树都是空的
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：LeetCode题解二叉树（四）：我要打十个？层序遍历变式九道-创新互联
当前URL：http://hbruida.cn/article/cdjoed.html

LeetCode题解二叉树（四）：我要打十个？层序遍历变式九道-创新互联

其他资讯