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

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();