[LeetCode-11] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1\2/3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

For recursion version, it's very easy to write.

But for iterative version, we need a stack to help.

java recursion

public ArrayList<Integer> result;public ArrayList<Integer> inorderTraversal(TreeNode root) {result = new ArrayList<Integer>();inorderTrRe(root);return result;}public void inorderTrRe(TreeNode root){if(root!=null){inorderTrRe(root.left);result.add(root.val);inorderTrRe(root.right);}}

java iterative

public class Solution {public ArrayList<Integer> result;public ArrayList<Integer> inorderTraversal(TreeNode root) {result = new ArrayList<Integer>();if(root== null) return result;inorderTraversal1(root);return result;}public void inorderTraversal1(TreeNode root) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode node = root;while(stack.size()>0 || node!=null){while(node != null){stack.push(node);node = node.left;}node = stack.pop();result.add(node.val);node = node.right;}}
}

c++ recursion

void inorder(TreeNode *root,vector<int> &path){if(root!=NULL){inorder(root->left,path);path.push_back(root->val);inorder(root->right,path);}}vector<int> inorderTraversal(TreeNode *root) {vector<int> path;if(root == NULL) return path;inorder(root, path);return path;}

c++ iterative

vector<int> inorderTraversal(TreeNode *root) {vector<int> path;stack<TreeNode*> stk;path.clear();if(root == NULL) return path;TreeNode *p = root;while(p != NULL || !stk.empty()){while(p!=NULL){stk.push(p);p = p->left;}p = stk.top();stk.pop();path.push_back(p->val);p = p->right;}return path;}