C#, recursion and iteration, simple and easy to understand.


  • 0

    Recursion
    I use global variable as node level to check case like "[],0" at my first version.
    But I found this version is better.

        public bool HasPathSum(TreeNode root, int sum) {
            if(root == null)return false;
            if(root.val == sum && root.left == null && root.right == null)return true;
            return HasPathSum(root.left, sum-root.val) || HasPathSum(root.right, sum-root.val);
        }
    

    Iteration

        public bool HasPathSum(TreeNode root, int sum) {
            if(root == null)return false;
            Stack<TreeNode> nodelist = new Stack<TreeNode>();
            nodelist.Push(root);
            while(nodelist.Count > 0)
            {
                TreeNode cur = nodelist.Pop();
                if(cur.left == null && cur.right == null && cur.val == sum) return true;
                if(cur.left != null)
                {
                    cur.left.val = cur.val + cur.left.val;
                    nodelist.Push(cur.left);
                }
                if(cur.right != null)
                {
                    cur.right.val = cur.val + cur.right.val;
                    nodelist.Push(cur.right);
                }
            }
            return false;
        }
    

Log in to reply
 

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