题解 | #二叉树中和为某一值的路径(一)#
二叉树中和为某一值的路径(一)
https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ function hasPathSum(root, sum) { // write code here if (!root) return false; return find(root, sum - root.val); } function find(node, count) { // 终止条件 if (!node.left && !node.right) { return count === 0; } // 还没到叶子节点,存在左子节点,就去递归看左边的路径情况 if (node.left) { if(find(node.left, count - node.left.val)) return true; } // 还没到叶子节点,存在右子节点,就去递归看右边的路径情况 if(node.right) { if(find(node.right, count - node.right.val)) return true; } // 上述情况都没有的情况下就返回false return false; } module.exports = { hasPathSum: hasPathSum, };
求从根节点到叶子节点是否存在一条路径使得路径和等于给定的sum。
深度搜索递归回溯,每次往下走一个节点,count -= node.val,终止的条件就是判断是否走到了叶子节点(!node.left && !node.right),走到了叶子节点之后有两种情况,此时count 等不等于0,等于0说明这条路径可行,否则不行。
下面两个递归,一个节点可行可不行,就是判断它的左右两个节点是否有返回true的,如果左子树边路径返回了true,那就说明左边路径可行,右子树同理。