leetcode之树的遍历总结

前言

刷leetcode的时候也看到几道遍历树的题目,刚看到还不太会做,不过掌握其通用算法基本上就能举一反三了.

题目介绍

题目大概就是如下图:

不知道其他人看到这题目啥想法,我第一想法觉得有点难,打算用迭代解决的,不过这个顺序不太好解决(实际上应该也可以,后面我在另外一题里面会说到,不过我用的不是这个方法),后来看到其他人的一些解题方法,他们有用的是stack,我借鉴了他们的思路,用的也是stack.
大概的思路是用两个stack储存TreeNode指针,一个叫curNodes,存储的是我们正在遍历的树的这一层次的指针,还有一个叫nextNodes,储存的是我们即将要遍历的树的下一层次的指针,还有一个leftToRight的布尔值来表示当前层次的遍历的顺序,举个例子,如果是true的话,就先向nextNodes中加入当前正在遍历的节点的左节点,然后再加入正在遍历的节点的右节点.由于stack是先进后出的,所以下次遍历的时候右节点会先被遍历到,
手画了一张图辅助理解,看图理解还是比较方便的.

大概意思是这样,剩下的都是一些边角的东西,我就不再赘述了.话不多说,直接上代码

/**
 * 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<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> result;
        if(!root)
            return result;

        stack<TreeNode*> curNodes;
        stack<TreeNode*> nextNodes;

        bool leftToRight = true;
        curNodes.push(root);
        while(!curNodes.empty())
        {
            vector<int> lineValue;
            while(!curNodes.empty())
            {
                TreeNode* node = curNodes.top();
                curNodes.pop();
                lineValue.push_back(node->val);
                if(leftToRight)
                {
                    if(node->left != NULL)
                        nextNodes.push(node->left);
                    if(node->right != NULL)
                        nextNodes.push(node->right);
                }
                else
                {
                    if(node->right != NULL)
                        nextNodes.push(node->right);
                    if(node->left != NULL)
                        nextNodes.push(node->left);
                }
            }
            result.push_back(lineValue);
            curNodes = nextNodes;
            stack<TreeNode*>().swap(nextNodes);/*这里用到了effective stl里面说的一个小的交换技巧,前几天在另外一篇博客里面总结了,学以致用嘛(笑)*/

            leftToRight = !leftToRight;
        }
        return result;
    }
};

相似题目

会了这道题,剩下的题目基本都差的不太多了,基本可以举一反三了.还有一个题和这个比较相似,题目如下图所示:

这个是顺序的遍历,不过我们需要注意的是,不能直接将leftToRight一直设为true就可以了,这样的话遍历的顺序会出问题(大家可以画了图来看看,和上面很类似的图,不过要注意遍历的顺序).
在这里,我由于思路是基于上一题的基础上,所以我的想法是把stack换成deque,加入元素的时候我用的是push_back,但是需要遍历节点的时候我用deque.front,然后再调用pop_front就可以了,这个思路还是比较直接的.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>> result;
        if(!root)
            return result;

        deque<TreeNode*> curNodes;
        deque<TreeNode*> nextNodes;

        curNodes.push_back(root);

        while(!curNodes.empty())
        {
            vector<int> lineValue;
            while(!curNodes.empty())
            {
                TreeNode* node = curNodes.front();
                curNodes.pop_front();
                lineValue.push_back(node->val);
                if(node->left != NULL)
                    nextNodes.push_back(node->left);
                if(node->right != NULL)
                    nextNodes.push_back(node->right);
            }
            result.push_back(lineValue);
            curNodes = nextNodes;
            deque<TreeNode*>().swap(nextNodes);

        }
        return result;
    }
};

变体

题目大概是下图所示:

这个变体其实挺没意思的(笑),如果从解题的角度,直接把上一题的结果reverse一下就可以了,不过从学习的角度来看,这样做就不太合适了,于是我看了看discuss区的其他人的解法,看到了一个不错的迭代的解法,不过结果也是用的reverse(不过可以换个容器例如deque解决这个需要reverse的问题).这个解法用的递归,是很聪明的解法.

vector<vector<int> > res;
void DFS(TreeNode* root, int level)
{
    if (root == NULL) return;
    if (level == res.size()) // The level does not exist in output
    {
        res.push_back(vector<int>()); // Create a new level
    }
    res[level].push_back(root->val); // Add the current value to its level
    DFS(root->left, level+1); // Go to the next level
    DFS(root->right,level+1);
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
    DFS(root, 0);
    return vector<vector<int> > (res.rbegin(), res.rend());
}

这个算法的思路还是不错的,利用层次数作为索引,然后再添加数据,由这个可以联想到第一题,如果我们再加一个leftToRight的标志,就可以实现第一题的要求了,不过需要注意的是这个时候,我们不能使用vector,使用deque比较好,因为我们需要在容器的头部加入元素,而在vector的头部加入元素是效率极低的行为,用了deque之后,我们利用vector v(deque.cbegin(),deque.cend()),就完成拷贝到vector的行为了.

总结:树的遍历是一个挺有意思的话题,出名的也有DFS和BFS算法,树的规律性很强,所以我们要学会找到规律,然后用循环或者递归实现,这样便能大大提高效率.