lintcode binary-tree-level-order-traversal 二叉樹的層次周遊

問題描述

lintcode

筆記

關鍵點，是要建立隊列來實作廣度優先周遊，同時以NULL來标記每一層的結束，有點神奇啊。

代碼

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here
        vector<vector<int>> res;
        res.clear();
        if (root == NULL)
            return res;
        std::queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> tmp;
        tmp.clear();
        while(!q.empty())
        {
            TreeNode *nowNode = q.front();
            q.pop();
            if (nowNode != NULL)
            {
                tmp.push_back(nowNode->val);
                if (nowNode->left != NULL)
                    q.push(nowNode->left);
                if (nowNode->right != NULL)
                    q.push(nowNode->right);
            }
            else
            {
                if (!tmp.empty())//KEY. if we dont write this, we will keep pushing NULL in the queue at the end of the traversal so that the while loop will never end.
                {
                    res.push_back(tmp);
                    tmp.clear();
                    q.push(NULL);
                    // WHY? USE NULL TO SPLIT DIFFERENRT LEVEL.
                    //IF q.front == NULL means that this level is finished. and all next level is in the queue.
                    // so that we can put NULL into the queue. 
                }
            }
        }
        return res;
    }
};
           

二次練習

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here
        vector<vector<int>> res;
        if (root == NULL)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> tmp;
        while (!q.empty())
        {
            TreeNode* nowNode = q.front();
            q.pop();
            if (nowNode)
            {
                tmp.push_back(nowNode->val);
                if (nowNode->left)
                    q.push(nowNode->left);
                if (nowNode->right)
                    q.push(nowNode->right);
            }
            else// 遇到一個NULL，說明周遊完了一層
            {
                if (!tmp.empty())// 注意加入這個判斷來防止一直往空隊列中插入NULL，導緻死循環
                {
                    res.push_back(tmp);
                    tmp.clear();
                    q.push(NULL);// 既然周遊完了一層，那就在隊列中再插入一個NULL來标記目前這一層的結束。
                }
            }
        }

    }
};