C# accepted, recursive and non-recursive, around 190ms


  • 0
    R

    Two methods:

    // 196ms Recursive
        public int SumNumbers(TreeNode root)
        {
            int global = 0;
            PreOrderSum(root, 0, ref global);
            return global;
        }
    
        private void PreOrderSum(TreeNode root, int currentSum, ref int globalSum)
        {
            if (root != null)
            {
                currentSum = currentSum * 10 + root.val;
                if (root.left == null && root.right == null)
                {
                    globalSum += currentSum;
                }
                PreOrderSum(root.left, currentSum, ref globalSum);
                PreOrderSum(root.right, currentSum, ref globalSum); 
            }
        }
        
    // 188ms Non-Recursive
        public int SumNumbers2(TreeNode root)
        {
            int result = 0;
            
            // pre order
            Stack<TreeNode> s = new Stack<TreeNode>();
            Stack<int> v = new Stack<int>();
            TreeNode temp = root;
            int sum = 0;
            while (s.Count > 0 || temp != null)
            {
                while (temp != null)
                {
                    sum = sum * 10 + temp.val;
                    s.Push(temp);
                    v.Push(sum);
                    temp = temp.left;
                }
    
                if (s.Count > 0)
                {
                    temp = s.Pop();
                    sum = v.Pop();
                    if (temp.left == null && temp.right == null)
                    {
                        result += sum;
                    }
    
                    // move to right
                    temp = temp.right;
                }
                else
                {
                    temp = null;
                }
            }
    
            return result;
        }

Log in to reply
 

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