Given a binary tree, return the preorder traversal of its nodes‘ values.
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
如下是非递归版本。
void preorderNonRecursiveTraversal(TreeNode*pRoot, vector<int>& result) { if (pRoot == NULL) return; stack<TreeNode*> st; TreeNode* temp; st.push(pRoot); while (!st.empty()) { temp = st.top(); result.push_back(temp->val); st.pop(); if (temp->right != NULL)st.push(temp->right);//先右 后左 if (temp->left != NULL)st.push(temp->left); } } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if (root == NULL) return result; preorderNonRecursiveTraversal(root, result); return result; }
递归版本：
void PreOrder(TreeNode* pRoot, vector<TreeNode*>& result) { if (pRoot != NULL) { result.push_back(pRoot); PreOrder(pRoot->left, result); PreOrder(pRoot->right, result); } }
[leetcode-144-Binary Tree Preorder Traversal]
原文：http://www.cnblogs.com/hellowooorld/p/6441897.html