【JZOF】82二叉树中和为某一值的路径(一)

题目描述：

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点。
2.叶子节点是指没有子节点的节点。
3.路径只能从父节点到子节点，不能从子节点到父节点。
4.总节点数目为n。

一、递归遍历：

import java.util.*;

public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null ) {
            return false;
        }

        if (sum == root.val && root.left == null && root.right == null) {
            return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

二、层次遍历

import java.util.*;

 

 public class Solution {
  
  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 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;
  }
}