Binary Tree Inorder Traversal


@ManuelP Thank you for your advice. Actually, I do not destroy the tree, I construct the tree just want to understand easier. but you are right, it is not an official way to explain this way

@monkeykingyan You do destroy the tree. When you're done, it's not the same as it was in the beginning. It's very different.
And btw it's not space complexity O(1). Because your ArrayList uses linear extra space (both extra capacity at all times, and duplicate space whenever it grows its capacity and copies its elements).

@flgt Yes, the example should be as same as the 3rd one, I will contact LeetCode to change it, thank you for letting me know


C++ solution
Using a variable to determine whether to go left or rightclass Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> vals; if (!root) return vals; stack<TreeNode*> stk; stk.push(root); bool goRight = false; while (!stk.empty()) { TreeNode *tmp = stk.top(); if (goRight) { vals.push_back(tmp>val); stk.pop(); if (tmp>right) { stk.push(tmp>right); goRight = false; } } else { if (tmp>left) { stk.push(tmp>left); } else { goRight = true; } } } return vals; } };

I guess I was closer to the first answer.
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
return helper(root, new ArrayList<Integer>());} private List<Integer> helper(TreeNode root, List<Integer> list) { if (root == null) { return list; } list = helper(root.left, list); list.add(root.val); list = helper(root.right, list); return list; }
}
:/

The Answer1
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list =new ArrayList<>();
inorder(root, list);
return list;
}
public void inorder(TreeNode root,List<Integer> list) {
if(root == null) return;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}

the tree is modified through the traversal, it can be reverted back to its original shape after the completion.
Check this link: https://www.geeksforgeeks.org/inordertreetraversalwithoutrecursionandwithoutstack/

Morris traversal should be O(1) extra space. You cant count the solution set as extra space since that was what was asked in the first place.
The whole point of Morris traversal is to eliminate the need for extra space(either call stack or stack in interative method).
No point of doing all that extra work of modifying all the nodes for no gain in time or space complexity.

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) return res; List<Integer> resl = inorderTraversal(root.left); List<Integer> resr = inorderTraversal(root.right); res.addAll(resl); res.add(root.val); res.addAll(resr); return res; }