Java O(1) space Morris Traversal Solution


  • 0
    V
    public class Solution {
        public int sumOfLeftLeaves(TreeNode root) {
            int sum = 0;
            boolean is_left = false;
            
            while(root != null)
            {
                if(root.left == null)
                {
                    root = root.right;
                }
                else
                {
                    TreeNode temp = root.left;
                    while(temp.right != null && temp.right != root)
                    {
                        temp = temp.right;
                        is_left = false;
                    }
                        
                    if(temp.right == null)
                    {
                        temp.right = root;
                        root = root.left;
                        is_left = true;
                    }
                    else if(temp.right == root)
                    {
                        root = temp.right.right;
                        temp.right = null;
                        if(temp.left == null && is_left) sum += temp.val;
                        is_left = false;
                    }
                }
            }
            
            return sum;
        }
    }
    

Log in to reply
 

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