[算法]路径总和——LeetCode.112

题目链接 菜死了 QAQ，果然好久没有刷树的题都傻了，接下开就专攻树了

果然每回都能踩到不同的坑

本地跑没错，在线立刻wa

思路

显然直接前序遍历树即可，如果忘了递归的流程建议直接手写或者跑个测试看看，判断条件记得是叶子到根，盲猜肯定有非叶子路径但是刚好相等的样例

最好最好 不要用全局变量（不能用public而应该用private）  废了我好久好久，死活想不通为啥出现本地对在线wa的灵异局面，直接暴力用个LinkedList存，所以内存消耗贼大2333（用int数组应该也行）

题解代码

完整可运行

package com.leaf;

import java.util.LinkedList;

public class HasPathSum {

	public static void main(String[] args) {
		TreeNodex one = new TreeNodex(5);
		TreeNodex two = new TreeNodex(4);
		TreeNodex three = new TreeNodex(8);
		TreeNodex four = new TreeNodex(11);
		TreeNodex five = new TreeNodex(13);
		TreeNodex six = new TreeNodex(4);
		TreeNodex seven = new TreeNodex(7);
		TreeNodex eight = new TreeNodex(2);
		TreeNodex nine = new TreeNodex(1);
		one.left = two;
		one.right = three;
		two.left = four;
		four.left = seven;
		four.right = eight;
		three.left = five;
		three.right = six;
		six.right = nine;
		
		TreeNodex text = new TreeNodex(0);
		TreeNodex text2 = new TreeNodex(1);
		TreeNodex text3 = new TreeNodex(1);
		text.left = text2; 
		text.right = text3;
		
		System.out.println(hasPathSum(text,1));
	}
	
	
        static boolean flag = false;	//不能用全局变量
	public static boolean hasPathSum(TreeNodex root, int sum) {
		LinkedList ls = new LinkedList();
		if(root==null) {	//为空的情况
			return false;
		}
		
		PathSum(root,sum,0,ls);
		System.out.println(ls.size());
		if(ls.size()!=0) {
			return true;
		}else {
			return false;
		}
		
    }
	
	// [1] 0的情况？？？
	public static boolean PathSum(TreeNodex root, int sum,int until,LinkedList ls) {
		
		until += root.val;
		
		if(root.left==null&&root.right==null&&until==sum) {
			ls.add(1);
		}
		
		if(root.left!=null) {
			TreeNodex te = root.left;
			PathSum(te,sum,until,ls);
		}
		
		if(root.right!=null) {
			TreeNodex te = root.right;
			PathSum(te,sum,until,ls);
		}
		return flag;
	}
	
}

class TreeNodex {
	 int val;
	 TreeNodex left;
	 TreeNodex right;
	 TreeNodex(int x) { 
		 val = x; 
	}
}

心得

1. 尽量不要用全局变量，样例一多必出问题。
2. 递归过程中的return没有作用，只有递归结束后那个return 有用，具体原因待查明。
3. 注意为空的情况，力扣经常出这种样例。
4. 注意路径不唯一的情况，当然结果重复对于大多数解法来说基本没有影响。