优于网上博客(新思路,省掉一个循环):102. Binary Tree Level Order Traversal BFS


题目链接: https://leetcode.com/problems/ ... tion/

网上博客C++写法基本是遍历一遍队列,这里提供另一个思路,就是利用BFS的特性,每次出队的都是步数最少的解,那么当步数增大,就说明后面所有的步数都只会大于等于当前节点。如此,我们只需要在步数变大的时候保存答案就搞定了。
class Node{
public:
    TreeNode *root;
    int step;
    Node(TreeNode *v, int s){
        root = v, step = s;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        ans.clear();
        if (root == NULL) return ans;
        
        Node firstNode(root, 0); 
        que.push(firstNode);
        
        int curLayer = 0;
        vector<int> curResult;
        while (!que.empty()){
            Node curNode = que.front();
            que.pop();
            
            if (curNode.step > curLayer){
                curLayer = curNode.step;
                ans.push_back(curResult);
                curResult.clear();
            }
            
            curResult.push_back(curNode.root->val);
            if (curNode.root->left != NULL){
                que.push(Node(curNode.root->left, curNode.step + 1));
            }
            if (curNode.root->right != NULL){
                que.push(Node(curNode.root->right, curNode.step + 1));
            }
        }
        ans.push_back(curResult);
        return ans;
    }
    
private:
    vector<vector<int>> ans;
    queue<Node> que;
};
已邀请:

要回复问题请先登录注册

返回顶部