程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 102 Binary Tree Level Order Traversal(二叉樹的層級順序遍歷)(*)

LeetCode 102 Binary Tree Level Order Traversal(二叉樹的層級順序遍歷)(*)

編輯:關於C++

翻譯

給定一個二叉樹,返回按層級順序遍歷的每個節點的值。

從左到右,逐層遍歷。

例如:
給定一個二叉樹 {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
返回它的層級順序遍歷結果為:
[
  [3],
  [9,20],
  [15,7]
]

翻譯

Given a binary tree, return the level order traversal of its nodes' values. 

(ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

分析

這道題和上一題是一毛一樣的,我就直接復制了。

首先定義了用於最後返回的vecAns,而後判斷root是否為空,是的話直接返回不做添加操作。構造的queue中int用於存放層級信息,TreeNode*用於存放節點。

vector> vecAns;
if (!root) return vecAns;
queue> queueTree;

接下來定義了map,它的優勢在於可以隨時指定鍵來添加值,這裡就是指定層級來添加信息,後面的是vector就是用於存放樹節點的。root的層級設定為0,後面用make_pair來構造pair對,最後添加到queue中。

map> mapAns;
int rootLevel = 0,  currentLevel =0;
queueTree.push(make_pair(rootLevel, root));

只要queue不為空就一直循環。每次一開始就解析出當前隊列頂部的層級信息以及當前節點,將它添加到map中。添加完之後就可以彈出了。繼續判斷左右子樹,如果為空就先添加到queue中等待下一部操作。待到下一次循環時,就是將它們添加到map中了。

while (!queueTree.empty()) {
    currentLevel = (queueTree.front().first);
    TreeNode *currentNode = (queueTree.front().second);
    mapAns[currentLevel].push_back(currentNode->val);
    queueTree.pop();
    if (currentNode->left != NULL)
        queueTree.push(make_pair(currentLevel + 1, currentNode->left));
    if (currentNode->right != NULL)
        queueTree.push(make_pair(currentLevel + 1, currentNode->right));
}            

將map中的信息逐個push到vector裡,最後就直接return了。

for (auto iter = mapAns.rbegin(); iter != mapAns.rend(); ++iter) {
    vecAns.push_back(iter->second);
}
return vecAns;

這是上一題的解法,現在的輸出順序和之前是相反的。既然是map,我們完全可以根據層級信息的隨意輸出了。

for (int i = 0; i <= currentLevel; ++i) {
    vecAns.push_back(mapAns[i]);
}

Ok,大家可以去看看上一題:

LeetCode 107 Binary Tree Level Order Traversal II(二叉樹的層級順序遍歷2)(*)

代碼

/**
* 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:
    vector> levelOrder(TreeNode* root) {             
        vector> vecAns;
        if (!root) return vecAns;
        queue> queueTree;
        map> mapAns;
        int rootLevel = 0, currentLevel = 0;
        queueTree.push(make_pair(rootLevel, root));
        while (!queueTree.empty()) {
            currentLevel = (queueTree.front().first);
            TreeNode *currentNode = (queueTree.front().second);
            mapAns[currentLevel].push_back(currentNode->val);
            queueTree.pop();
            if (currentNode->left != NULL)
                queueTree.push(make_pair(currentLevel + 1, currentNode->left));
            if (currentNode->right != NULL)
                queueTree.push(make_pair(currentLevel + 1, currentNode->right));
        }
        for (int i = 0; i <= currentLevel; ++i) {
            vecAns.push_back(mapAns[i]);
        }
        return vecAns;               
    }
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved