CodeCollection2018
9/13/2019 - 1:59 PM

二叉树的路径和系列问题

I II III IV 第二种是选出所有的等于sum值的路径，和第一种一样的做法。这些涉及到二叉树路径的问题，都是前序遍历或者是逆先序遍历，只是说在遍历过程中需要对每一个节点进行的处理不同。递归调用的时候可以先left然后再right，也可以是先right然后再left。。、

I--recursive
content_copyfile_download
//给定一个目标值，确定一棵二叉树中是否存在从根节点到叶子节点的路径其中节点之和等于目标值
public boolean hasPath(TreeNode root,int target){
  if(root==null) return true;
  return hasPath_(root,target,0);
  
}
public boolean hasPath_(TreeNode root,int target,int sum){
  if(root.left==null && root.right==null && sum+root.val==target) return true;
  else if(root.left==null && root.right==null && sum+root.val!=target) return false;
  boolean res = false;
  if(root.left!=null) res |= hasPath_(root.left,target,sum+root.val);
  if(res==true) return true;
  if(root.right!=null) res |= hasPath_(root.right,target,sum+root.val);
  return res;
}
I--recurrent
content_copyfile_download
//循环地遍历，前序遍历
public boolean hasPathToSum(TreeNode root,int sum){
  if(root==null) return false;
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  while(!stack.isEmpty()){
    TreeNode cur = stack.top();stack.pop();
    if(cur.left==null && cur.right==null && cur.val==sum) return true;
    if(cur.left!=null){
      cur.left.val += cur.val;
      stack.push(cur.left);
    }
    if(cur.right!=null){
      cur.right.val += cur.val;
      stack.push(cur.right);
    }
  }
  return false;
}
III
content_copyfile_download
//给定二叉树和一个sum值，选择所有加和等于sum的路径，但是这个路径不一定是从根节点开始到叶子结点结束的。
//实际这就是给定一个数组，然后求其中子集问题，只是这里采用树型结构来组织数据而已，采用的还是0/1思想和递归方法，对于树中的每一个节点，如果它的父节点不要则该节点就有两种选择一个是要一个是不要，可是如果父节点加上了那就必须要该节点了。
public int numOfPathToSum(TreeNode root,int sum){
  
}
IV
content_copyfile_download
//用一个三位数表示树中的节点的level，position和value。计算所有从root到leaf的路径之和的和
public int pathSum(int[] nums){
    if(nums==null || nums.length==0) return 0;
    int res = 0 ;
    Map<Integer,Integer> m = new HashMap<>();
    for(int num : nums) m.push(num/10,num%10);
    helper(nums[0]/10,m,0,res);
    return res;
}
public void helper(int num,Map<Integer,Integer> m,int cur,int& res){
    int level = num/10,pos=num%10;
    int left = (level+1)*10+2*pos-1,right=left+1;
    cur += m.get(num);
    if(m.get(left)==null && m.get(right)==null){
        res += cur;
        return;
    }
    if(m.get(left)!=null) helper(left,m,cur,res);
    if(m.get(right)!=null) helper(right,m,cur,res);
}