題目
解析
拿到這道題的第一個想法就是算出從根結(jié)點到葉子結(jié)點的和的所有情況然后比較是否和sum相同杭措，所以肯定是要用到遞歸的广鳍。先從最簡單的一種情況開始分析：
5作為根結(jié)點蛙婴，先判斷4結(jié)點下面是否有葉子結(jié)點欺劳，沒有則判斷5+4是否等于sum（根結(jié)點+左葉）这敬，如果等于sum，那么就找到了答案媳叨，如果不等于sum腥光，那么就判斷5+8是否等于sum（根結(jié)點+右葉）关顷。如果4下面有葉子結(jié)點，也就是下面這種情況：
根據(jù)上面一步武福，我們已經(jīng)計算出（5+4）和（5+8）了议双，發(fā)現(xiàn)其都不等于sum，這個時候就需要往下繼續(xù)尋找了捉片，把（5+4）的值保存起來平痰，然后再加上此時的左葉結(jié)點的值11，或者把（5+8）的值保存起來伍纫，然后加上此時的左葉結(jié)點/右葉結(jié)點計算判斷是否和sum相等宗雇，以此類推。
此時莹规，我們便可以抽象出一個簡單的算法流程
當(dāng)然赔蒲，這都是要在還未找到匹配值以及node結(jié)點不空的情況下才成立的。
下面附上代碼.
代碼
public class Main {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(5);
t1.left = new TreeNode(4);
t1.right = new TreeNode(8);
t1.left.left = new TreeNode(11);
t1.right.left = new TreeNode(13);
t1.right.right = new TreeNode(4);
t1.left.left.left = new TreeNode(7);
t1.left.left.right = new TreeNode(2);
t1.right.right.right = new TreeNode(1);
// TreeNode t2 = new TreeNode(1);
Main main = new Main();
System.out.println(main.hasPathSum(t1, 1));
}
boolean isOk = false;
public boolean hasPathSum(TreeNode root, int sum) {
handle(root, 0, sum);
return isOk;
}
public void handle(TreeNode node, int temp, int sum) {
if (!isOk && node != null) {
if (node.left == null && node.right == null && node.val + temp == sum) {
isOk = true;
}
if (node.left != null) {
handle(node.left, node.val + temp, sum);
}
if (node.right != null) {
handle(node.right, node.val + temp, sum);
}
}
}
