112. 路径总和

image.png
image.png

回溯

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean hasPathSum(TreeNode root, int targetSum) {
  18.         if(root == null ) return false;
  19.         return traversal(root,targetSum - root.val);
  20.     }
  22.     public boolean traversal(TreeNode cur, int count ) {
  23.         // 遇到叶子节点，并且计数为0
  24.         if( cur.left == null && cur.right == null && count == 0 ) return true;
  25.         // 遇到叶子节点直接返回
  26.         if( cur.left == null && cur.right == null ) return false;
  28.         if(cur.left != null ) {  // 左
  29.             count -= cur.left.val;  // 递归，处理节点;
  30.             if(traversal(cur.left,count) ) return true;
  31.             count += cur.left.val; // 回溯，撤销处理结果
  32.         }
  33.         if(cur.right != null ) {
  34.             count -= cur.right.val;  // 递归，处理节点;
  35.             if(traversal(cur.right,count) ) return true;
  36.             count += cur.right.val; // 回溯，撤销处理结果
  37.         }
  39.         return false;
  40.     }
  41. }

回溯

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean hasPathSum(TreeNode root, int targetSum) {
  18.         if(root == null ) return false;
  20.         // 叶子节点判断是否符合
  21.         if(root.left == null && root.right == null ) return root.val == targetSum;
  24.         // 求两侧分支的路径和
  25.         return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
  26.     }
  27. }