陈中正的网络日志

Leetcode: Binary Tree Preorder Traversal

题目

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

分析

  1. 第一种方法采用递归版先序遍历。

  2. 第二种方法用循环和递归实现迭代版先序遍历。

代码

递归版

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        preorder(root);

        return res;
    }

    void preorder(TreeNode *root)
    {
        if (!root)
            return;

        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
private:
    vector<int> res;
};

迭代版

class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        while (true)
        {
            preorder(root);
            if (stk.empty())
                break;
            root = stk.top();
            stk.pop();
        }
        return res;
    }
    void preorder(TreeNode *root)
    {
        while (root)
        {
            res.push_back(root->val);
            if (root->right)
                stk.push(root->right);
            root = root->left;
        }
    }

private:
    vector<int> res;
    stack<TreeNode *> stk;
};

参考

《数据结构》 邓俊辉

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38942895

Categories:  OJ题解 

« Shell脚本: Windows下可用源码 转换为 Linux下可用源码 Leetcode: Sum Root to Leaf Numbers »