13.路徑總和

13.1問(wèn)題

給你二叉樹(shù)的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum 。判斷該樹(shù)中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。如果存在，返回 true ；否則，返回 false 。

葉子節(jié)點(diǎn) 是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

• 示例一：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目標(biāo)和的根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑如上圖所示。

13.2解法一：遞歸

13.2.1遞歸思路

（1）確定遞歸函數(shù)參數(shù)以及返回值

• 參數(shù)：節(jié)點(diǎn)、計(jì)數(shù)器（記錄從根節(jié)點(diǎn)到該節(jié)點(diǎn)的值）、targetSum
• 返回值：需要搜索整棵二叉樹(shù)并且需要處理遞歸返回值的遞歸函數(shù)就需要返回值，此題使用boolean代表這顆樹(shù)是否存在路徑總和為targetSum的路徑

private boolean traversal(TreeNode node,int count,int targetSum)

（2）確定終止條件

• 當(dāng)當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)并且count=targetSum時(shí)，返回true（該count已經(jīng)包含當(dāng)前節(jié)點(diǎn)的值了）；
• 當(dāng)當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，直接返回false

if(node.left==null && node.right==null && count==targetSum){return true;
}
if(node.left==null && node.right==null){return false;
}

（3）確定遞歸邏輯

• 因?yàn)榻K止條件是判斷葉子節(jié)點(diǎn)，所以遞歸的過(guò)程中就不要讓空節(jié)點(diǎn)進(jìn)入遞歸了；
• 若該節(jié)點(diǎn)的左右孩子非空，則遞歸（注意遞歸函數(shù)的count加上左右孩子的值）；
• 遞歸完若發(fā)現(xiàn)為true，則直接返回true，否則進(jìn)行回溯，不要該左孩子節(jié)點(diǎn)（count減去該值），進(jìn)行右孩子節(jié)點(diǎn)的查找（回溯）；

if(node.left!=null){if(traversal(node.left,count+=node.left.val,targetSum)){return true;}//回溯count-=node.left.val;
}
if(node.right!=null){if(traversal(node.right,count+=node.right.val,targetSum)){return true;1}//回溯count-=node.right.val;
}
return false;

13.2.2代碼實(shí)現(xiàn)

public boolean hasPathSum(TreeNode root, int targetSum) {if(root==null){return false;}return traversal(root,root.val,targetSum);}private boolean traversal(TreeNode node,int count,int targetSum){if(node.left==null && node.right==null && count==targetSum){return true;}if(node.left==null && node.right==null){return false;}if(node.left!=null){if(traversal(node.left,count+=node.left.val,targetSum)){return true;}//回溯count-=node.left.val;}if(node.right!=null){if(traversal(node.right,count+=node.right.val,targetSum)){return true;}//回溯count-=node.right.val;}return false;}
}

14.路徑總和 ||

14.1問(wèn)題

給你二叉樹(shù)的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和 的路徑。

葉子節(jié)點(diǎn) 是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

• 示例一：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]

14.2解法一：遞歸

14.2.1遞歸思路

（1）確定遞歸函數(shù)參數(shù)以及返回值

• 參數(shù)說(shuō)明：
  • 求根節(jié)點(diǎn)到 node 節(jié)點(diǎn)的路徑之和 == targetSum
  • paths存放當(dāng)前路徑
  • res存放符合路徑總和為targetSum的路徑
  • count代表從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑中和
• 無(wú)返回值

private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum)

（2）確定終止條件

• 若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則判斷count==targetSum，符合則添加該paths到res中，否則返回

if(node.left==null && node.right==null){if(count==targetSum)    {res.add(new ArrayList<>(path));}return;
}

（3）確定遞歸邏輯

if(node.left!=null){paths.add(node.left.val);traversal(node.left,paths,res,count+=node.left.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.left.val;
}if(node.right!=null){paths.add(node.right.val);traversal(node.right,paths,res,count+=node.right.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.right.val;
}

14.2.2代碼實(shí)現(xiàn)

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {int count=0;List<List<Integer>> res=new ArrayList<>();List<Integer> paths=new ArrayList<>();if(root==null){return res;}paths.add(root.val);traversal(root,paths,res,count+=root.val,targetSum);return res;}private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> res, int count, int targetSum){if(node.left==null && node.right==null){if(count==targetSum){res.add(new ArrayList<>(paths));}return;}if(node.left!=null){paths.add(node.left.val);traversal(node.left,paths,res,count+=node.left.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.left.val;}if(node.right!=null){paths.add(node.right.val);traversal(node.right,paths,res,count+=node.right.val,targetSum);//回溯paths.remove(paths.size()-1);count-=node.right.val;}}
}