层层遍历树

// ----------------------  层层遍历树  ------------------------ //

// 笨方法
typedef struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} TNode;

static TNode root;

void visit_node(TNode *node, int layer, int max_layer) {
    if (!node) return;
    if (layer > max_layer) return;
    cout<<"layer "<<layer<<": "<<node->val<<endl;
    int sl = ++layer;
    visit_node(node->left, sl, max_layer);
    visit_node(node->right, sl, max_layer);
}

int max_layer(TNode *root) {
    if(!root) return 0;
    if(!root->left && !root->right) return 1;
    int l = max_layer(root->left);
    int r = max_layer(root->right);
    int ret = l>r?l:r;
    return ++ret;
}

// 入口方法
void visit_tree(TNode *root) {
    int ml = max_layer(root);
    cout<<"max layer: "<<ml<<endl;
    visit_node(root, 1, ml);
}

/*------------------------------------------------------------------------*/

// 好方法
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > ret;
        if(!root) return ret;
        vector<int> vec;
        ret.push_back(vec);
        queue<TreeNode *> q;
        q.push(root);
        int l1 = 1, l2 = 0, cl = 0;
        while(!q.empty()) {
            TreeNode *&f = q.front();
            q.pop(); --l1; ret[cl].push_back(f->val);
            if(f->left) {q.push(f->left); ++l2;}
            if(f->right) {q.push(f->right); ++l2;}
            if(l1 == 0) {
                l1 = l2;
                l2 = 0;
                if(!q.empty()) {
                    vector<int> vec;
                    ret.push_back(vec);
                    ++cl;
                }
            }
        }
        
        return ret;
    }
};

 

欢迎关注微信公众号——计算机视觉