IT博客汇 | LeetCode BFS(上)

LeetCode BFS(上)

一根稻草发表于 2014-12-21 00:00:00

这里是LeetCode BFS类型前半部分题目：

Binary Tree Zigzag Level Order Traversal
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal II
Clone Graph

1.Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7},

return its zigzag level order traversal as:

[  
  [3],  
  [20,9],  
  [15,7]  
]

struct ZigZag{
    TreeNode *node;
    int level;
    ZigZag(TreeNode *p, int n) : node(p), level(n){}
};
class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector <vector<int> > v;
        ZigZag pz(NULL,0);
        stack<ZigZag> sz;
        int child_level = 0;
        if (root)
        {
            sz.push(ZigZag(root,0));
        }
        while (!sz.empty())
        {
            pz = sz.top();
            sz.pop();
            if (v.size() < pz.level + 1)
            {
                vector<int> tmp_v;
                v.push_back(tmp_v);
            }
            if (pz.level % 2 == 1)
            {//from right to left
                v[pz.level].push_back(pz.node->val);
            }
            else
            {//from left to right
                v[pz.level].insert(v[pz.level].begin(), pz.node->val);
            }

            if (pz.node->left)
            {
                sz.push(ZigZag(pz.node->left, pz.level + 1));
            }
            if (pz.node->right)
            {
                sz.push(ZigZag(pz.node->right, pz.level + 1));
            }

        }
        return v;
    }
};

zigzag遍历很简单，但是我封装了TreeNode，新造了一个数据结构ZigZag来保存每一个节点的层次，不够优雅，有没有什么方法不用封装呢，看下面。

2.Binary Tree Level Order Traversal

ref

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},

return its level order traversal as:

[  
  [3],  
  [9,20],  
  [15,7]  
]

vector<vector<int> > levelOrder(TreeNode *root) 
{
    vector<vector<int> > v;
    typedef pair<TreeNode*, int> PAIR;
    queue<PAIR> q;

    if (root)
    {
        q.push(PAIR(root, 0));
    }
    while (!q.empty())
    {
        TreeNode *node = q.front().first;
        int level = q.front().second;
        q.pop();
        if (v.size() < level + 1)
        {
            vector<int> item;
            v.push_back(item);
        }
        v[level].push_back(node->val);

        if (node->left)
        {
            q.push(PAIR(node->left, level + 1));
        }
        if (node->right)
        {
            q.push(PAIR(node->right, level + 1));
        }
    }
    return v;
}

这里用pair来封装TreeNode，和新定义一个struct差不多，不过程序看起来更优美了。

3.Binary Tree Level Order Traversal II

ref

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

[
  [15,7],  
  [9,20],  
  [3]  
]

将Binary Tree Level Order Traversal 返回的数组reverse一下就可以了。

vector<vector<int> > levelOrderBottom(TreeNode *root) 
{
    vector<vector<int> > v;
    typedef pair<TreeNode*, int> PAIR;
    queue<PAIR> q;
    if (root)
    {
        q.push(PAIR(root, 0));
    }
    while (!q.empty())
    {
        TreeNode *node = q.front().first;
        int level = q.front().second;
        q.pop();
        if (v.size() < level + 1)
        {
            vector<int> item;
            v.push_back(item);
        }
        v[level].push_back(node->val);

        if (node->left)
        {
            q.push(PAIR(node->left, level + 1));
        }
        if (node->right)
        {
            q.push(PAIR(node->right, level + 1));
        }
    }
    //reverse v
    int n = v.size();
    for (int i = 0; i < n / 2; i++)
    {
        v[i].swap(v[n - 1 - i]);
    }
    return v;
}

4.Clone Graph

ref

在DFS系列里已经解决了这个问题==Clone Graph