LeetCode - Easy - 112. Path Sum

我就是我 2022-12-28 11:11 132阅读 0赞

# LeetCode - Easy - 112. Path Sum #

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/path-sum/][https_leetcode.com_problems_path-sum]

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

**Note**: A leaf is a node with no children.

**Example**:

Given the below binary tree and `sum = 22`,

5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

## Analysis ##

方法一：递归版的DFS

方法二：非递归版的DFS

方法三：别人写的递归版DFS

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PathSum { 
    
    	// 方法一：递归版DFS
    	public boolean hasPathSum1(TreeNode root, int sum) { 
    		return hasPathSum(root, 0, sum);
    	}
    
    	private boolean hasPathSum(TreeNode node, int currentSum, int sum) { 
    		if (node == null)
    			return false;
    
    		currentSum += node.val;
    
    		if (node.left == null && node.right == null) { 
    			return currentSum == sum;
    		}
    
    		return hasPathSum(node.left, currentSum, sum) || hasPathSum(node.right, currentSum, sum);
    	}
    
    	// 方法二：非递归版DFS
    	public boolean hasPathSum2(TreeNode root, int sum) { 
    		if (root == null)
    			return false;
    
    		LinkedList<Object> stack = new LinkedList<>();
    		TreeNode p = root;
    		int current = p.val;
    
    		while (true) { 
    
    			if (p.left != null && p.right != null) { 
    				stack.push(new Object[] {  p.right, current + p.right.val });
    				current += p.left.val;
    				p = p.left;
    			} else if (p.left != null && p.right == null) { 
    				current += p.left.val;
    				p = p.left;
    			} else if (p.left == null && p.right != null) { 
    				current += p.right.val;
    				p = p.right;
    			} else { 
    				if (current == sum)
    					return true;
    
    				if (stack.isEmpty()) { 
    					break;
    				} else { 
    					Object[] objs = (Object[]) stack.pop();
    					p = (TreeNode) objs[0];
    					current = (int) objs[1];
    				}
    			}
    		}
    
    		return false;
    	}
    
    	// 方法三：别人写的递归版DFS
    	public boolean hasPathSum3(TreeNode root, int sum) { 
    		if (root == null)
    			return false;
    
    		if (root.left == null && root.right == null && sum - root.val == 0)
    			return true;
    
    		return hasPathSum3(root.left, sum - root.val) || hasPathSum3(root.right, sum - root.val);
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PathSumTest { 
    
    	@Test
    	public void test1() { 
    		PathSum obj = new PathSum();
    
    		TreeNode root = new TreeNode(5);
    		
    		root.left = new TreeNode(4);
    		root.right = new TreeNode(8);
    		
    		root.left.left = new TreeNode(11);
    		
    		root.left.left.left = new TreeNode(7);
    		root.left.left.right = new TreeNode(2);
    		
    		root.right.left = new TreeNode(13);
    		root.right.right = new TreeNode(4);
    		
    		root.right.right.right = new TreeNode(1);
    
    		assertTrue(obj.hasPathSum1(root, 22));
    		assertTrue(obj.hasPathSum2(root, 22));
    		assertTrue(obj.hasPathSum3(root, 22));
    	}
    	
    	@Test
    	public void test2() { 
    		PathSum obj = new PathSum();
    		
    		TreeNode root = new TreeNode(1);
    		root.left = new TreeNode(2);
    		
    		assertFalse(obj.hasPathSum1(root, 1));
    		assertFalse(obj.hasPathSum2(root, 1));
    		assertFalse(obj.hasPathSum3(root, 1));
    	}
    }

[https_leetcode.com_problems_path-sum]: https://leetcode.com/problems/path-sum/