题解 | #二叉树中和为某一值的路径(一)#

递归

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

时间复杂度和空间复杂度都是O(n)，n是二叉树中节点的个数。

非递归

使用栈来实现非递归的解法。需要维护两个栈，一个栈存储当前节点，另一个栈存储从根节点到当前节点的路径上节点值之和。

首先将根节点和它的值入栈。然后进行循环，直到栈为空为止。在循环中，取出当前节点和它的路径和，如果当前节点是叶子节点，并且路径和等于目标值sum，则返回true。如果当前节点不是叶子节点，则将当前节点的左右子节点和它们的路径和分别入栈。

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    Stack<TreeNode> nodeStack = new Stack<>();
    Stack<Integer> sumStack = new Stack<>();
    nodeStack.push(root);
    sumStack.push(sum - root.val);
    while (!nodeStack.isEmpty()) {
        TreeNode node = nodeStack.pop();
        int pathSum = sumStack.pop();
        if (node.left == null && node.right == null && pathSum == 0) {
            return true;
        }
        if (node.left != null) {
            nodeStack.push(node.left);
            sumStack.push(pathSum - node.left.val);
        }
        if (node.right != null) {
            nodeStack.push(node.right);
            sumStack.push(pathSum - node.right.val);
        }
    }
    return false;
}

时间复杂度和空间复杂度也都是O(n)，n是二叉树中节点的个数。

栈也可换为队列：

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<Integer> sumQueue = new LinkedList<>();
    nodeQueue.offer(root);
    sumQueue.offer(sum - root.val);
    while (!nodeQueue.isEmpty()) {
        int size = nodeQueue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = nodeQueue.poll();
            int pathSum = sumQueue.poll();
            if (node.left == null && node.right == null && pathSum == 0) {
                return true;
            }
            if (node.left != null) {
                nodeQueue.offer(node.left);
                sumQueue.offer(pathSum - node.left.val);
            }
            if (node.right != null) {
                nodeQueue.offer(node.right);
                sumQueue.offer(pathSum - node.right.val);
            }
        }
    }
    return false;
}