Binary Tree Inorder Traversal


  • 1

    Click here to see the full article post


  • 0
    C

    The Morris traversal method is truly amazing !! very creative approach


  • 0

    Data Structure is amazing!


  • 0

    That's not Morris traversal, since that doesn't destroy the tree (which yours does).


  • 0

    @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


  • 0
    F

    The example answer should be [4,2,5,1,3,6]..... The animation is wrong also.


  • 0

    @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).


  • 0

    @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


  • 0

    @ManuelP Yes, thank you for letting me know, Space Complexity should be O(n).


  • 0
    C

    science technichian


  • 0
    R

    C++ solution
    Using a variable to determine whether to go left or right

    class 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;
        }
    };
    

  • -1
    J

    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;  
    }
    

    }

    :/


  • -1
    W

    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);
    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.