[JZOF] 82 binary tree with a path of a certain value (1)

题目描述：

给定一个二叉树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 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;
      // 内部类,Associate a partial path sum with the current node
      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;
      }
      // Use a queue to store nodes during traversal
      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;
  }
}