C# - iterative - standard in-order traversal - simple with explaination


  • 0

    To find all the left leaves you will need to traverse the whole tree, so here I just go with standard in-order traversal and check each node for any "left leaves" and add those to the total. You could argue that once you've found a left leaf you don't need to traverse that node, but this will not save much of anything worthwhile so you may as well keep it simple with standard traversal.

        public int SumOfLeftLeaves(TreeNode root) 
        {
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            int sum = 0;
    
            while (node != null || stack.Count > 0)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    node = stack.Pop();
                    
                    // visit
                    if (node.left != null && node.left.left == null && node.left.right == null)
                    {
                        sum += node.left.val;                    
                    }
                    
                    node = node.right;
                }
            }
            
            return sum;
        }
    

Log in to reply
 

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