题解 | #二叉树中是否存在节点和为指定值的路径#

思路

本题实质上是一道二叉树搜索的问题，通过遍历搜索二叉树，从而判断二叉树节点中是否存在节点和为指定值的路径。

方法一：前序遍历

• 这里采用的是前序遍历的递归实现方法，即：根节点-左儿子-右儿子。

• 具体思路如下图所示：

  

• 具体代码如下：

  import java.util.*;
  /*
   * public class TreeNode {
   *   int val = 0;
   *   TreeNode left = null;
   *   TreeNode right = null;
   * }
   */
  public class Solution {
      /**
       * 
       * @param root TreeNode类 
       * @param sum int整型 
       * @return bool布尔型
       */
      public boolean hasPathSum (TreeNode root, int sum) {
          // 根节点为空，则直接返回false
          if (root == null){
              return false;
          }
          // 只有根节点，且值满足要求，则返回true
          if (root.left == null && root.right == null && root.val == sum){
              return true;
          }
          // 递归遍历
          return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
      }
  }

• 时间复杂度为，n为二叉树节点数，即最坏的情况需要遍历二叉树的所有节点。

• 空间复杂度为，最坏情况递归遍历所有节点N。

  方法二：层次遍历

• 同样我们也可以通过层次遍历，同步推进每一条路径在每一层的值，从而判断二叉树中是否存在节点和为指定值的路径。只需要去判断叶子节点的和是否为要求的值即可。

• 具体思路如下图所示：
  

• 代码如下：

  import java.util.*;
  
   /*
  * public class TreeNode {
  *   int val = 0;
  *   TreeNode left = null;
  *   TreeNode right = null;
  * }
  */
  
   public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    class Pair{
        TreeNode node = null;
        int curSum = 0;
        // 内部类，将部分路径和与当前节点相关联
        public Pair(TreeNode node,int curSum){
            this.node = node;
            this.curSum = curSum;
        }
    }
  
    public boolean hasPathSum (TreeNode root, int sum) {
        // 根节点为空，返回false
        if (root == null){
            return false;
        }
        // 使用队列在遍历过程中存储节点
        Queue<Pair> nodeQueue= new LinkedList<>();
        Pair pair = new Pair(root,root.val);
        nodeQueue.add(pair);
        Pair curPair = null;
        // 层次遍历,根，左，右
        while(!nodeQueue.isEmpty()){
            curPair = nodeQueue.poll();
            // 左节点非空
            if (curPair.node.left != null){
                nodeQueue.add(new Pair(
                    curPair.node.left,
                    curPair.curSum+curPair.
                    node.left.val));
            }
            // 右节点非空
            if (curPair.node.right != null){
                nodeQueue.add(new Pair(
                    curPair.node.right,
                    curPair.curSum+curPair.
                    node.right.val));
            }
            // 判断是否为叶子节点，是则与sum进行比较
            if (curPair.node.left==null&&curPair.node.right==null){
                if (sum == curPair.curSum){
                return true;
                }
            } 
        }
        return false;
    }
  }

• 时间复杂度为，n为二叉树节点数，最差需要遍历所有节点。

• 空间复杂度为，使用到了队列来记录节点，最差需要空间为n，即节点数。