【LeetCode】 112. 路径总和递归迭代

╰半夏微凉° 2021-06-10 20:37 374阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

两种解法，一种是递归，一种是用栈，我想到了用栈，但是没想到要用两个栈…

递归：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean hasPathSum(TreeNode root, int sum) { 
            if (root == null) return false;
            sum -= root.val;
            if (root.left == null && root.right == null) { 
                if (sum == 0) return true;
            }
            return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
        }
    }

迭代：

class Solution { 
      public boolean hasPathSum(TreeNode root, int sum) { 
        if (root == null)
          return false;
    
        LinkedList<TreeNode> node_stack = new LinkedList();
        LinkedList<Integer> sum_stack = new LinkedList();
        node_stack.add(root);
        sum_stack.add(sum - root.val);
    
        TreeNode node;
        int curr_sum;
        while ( !node_stack.isEmpty() ) { 
          node = node_stack.pollLast();
          curr_sum = sum_stack.pollLast();
          if ((node.right == null) && (node.left == null) && (curr_sum == 0))
            return true;
    
          if (node.right != null) { 
            node_stack.add(node.right);
            sum_stack.add(curr_sum - node.right.val);
          }
          if (node.left != null) { 
            node_stack.add(node.left);
            sum_stack.add(curr_sum - node.left.val);
          }
        }
        return false;
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/ac12ae06698649c09d282e90f2a0335b.png