阿飞算法|剑指offer-二叉树中和为某一值的路径(一)(多解法)
二叉树中和为某一值的路径(一)
http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
JZ82 二叉树中和为某一值的路径(一)
方法1:DFS
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
return dfs(root, sum);
}
private boolean dfs(TreeNode root, int sum) {
//当前节点是叶子节点,开始比较val是否相等
if (root.left == null && root.right == null && root.val == sum) return true;
boolean res = false;
//只要左右子树有一个是true即可
if (root.left != null) res = res || dfs(root.left, sum - root.val);
if (root.right != null) res = res || dfs(root.right, sum - root.val);
return res;
}
方法2:递归
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
//当前的节点是叶子节点,比较剩下的sum值是否相等
if (root.left == null && root.right == null) return root.val == sum;
//左右两棵子树只要一个符合即可
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
方法3:BFS
public boolean hasPathSum4th(TreeNode root, int sum) {
if (root == null) return false;
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
LinkedList<Integer> numQueue = new LinkedList<>();
nodeQueue.offer(root);
numQueue.offer(root.val);
while (!nodeQueue.isEmpty()) {
TreeNode curNode = nodeQueue.pop();
Integer curNum = numQueue.pop();
if (curNode.left == null && curNode.right == null && curNum == sum) return true;
if (curNode.left != null) {
nodeQueue.offer(curNode.left);
numQueue.offer(curNum + curNode.left.val);
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right);
numQueue.offer(curNum + curNode.right.val);
}
}
return false;
}