刷题94. Binary Tree Inorder Traversal

一、题目说明

题目94. Binary Tree Inorder Traversal，给一个二叉树，返回中序遍历序列。题目难度是Medium！

二、我的解答

用递归遍历，学过数据结构的应该都可以实现。

class Solution{

	public:

		vector<int> inorderTraversal(TreeNode* root){

			if(root != NULL){

				if(root->left !=NULL)inorderTraversal(root->left);

				res.push_back(root->val);

				if(root->right !=NULL)inorderTraversal(root->right);

			}

			return res;

		}

	private:

		vector<int> res;

};

Runtime: 4 ms, faster than 61.00% of C++ online submissions for Binary Tree Inorder Traversal.

Memory Usage: 10.5 MB, less than 5.00% of C++ online submissions for Binary Tree Inorder Traversal.

三、优化措施

用非递归算法，需要一个栈，代码如下：

class Solution{

	public:

		//iteratively

		vector<int> inorderTraversal(TreeNode* root){

			stack<TreeNode*> st;

			TreeNode* p = root;

			if(p != NULL){

				while(p !=NULL) {

					st.push(p);

					p = p->left;

				}

				while(!st.empty()){

					p = st.top();

					st.pop();

					res.push_back(p->val);

					if(p->right !=NULL) {

						p = p->right;

						while(p !=NULL) {

							st.push(p);

							p = p->left;

						}

					}

				}

			}

			return res;

		}

	private:

		vector<int> res;

};

性能：

Runtime: 4 ms, faster than 60.93% of C++ online submissions for Binary Tree Inorder Traversal.

Memory Usage: 9.2 MB, less than 89.00% of C++ online submissions for Binary Tree Inorder Traversal.

巴特西

刷题94. Binary Tree Inorder Traversal

最新文章

热门文章