递归
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; }