leetcode_112_Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

              5
             /             4   8
           /   /           11  13  4
         /  \              7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

public boolean hasPathSum(TreeNode root, int sum){
		int num=0;
		if (root == null)
			return false;
		Stack<TreeNode> st = new Stack<TreeNode>();
		Stack<TreeNode> st1 = new Stack<TreeNode>();
		st.push(root);
		num+=root.val;
		TreeNode top = null;
		while (!st.empty()) {
			top=st.peek();
			while(top.left!=null)//达到页结点
			{
				st.push(top.left);
				num+=top.left.val;
				top=top.left;
			}
			while(!st.empty())
			{
				top=st.peek();
				if(top.right==null)//无右子树时，访问结点
				{
					if(top.left==null&&num==sum)
						return true;
					st.pop();
					num-=top.val;
				}else 
				{
					if(st1.empty()||(!st1.empty()&&st1.peek()!=top))//有右子树且第一次出现，将右子树入栈，并将结点在st1中标记一下
					{
						st1.push(top);
						st.push(top.right);
						num+=top.right.val;
						break;//右子树入栈了，然后从右子树开始
					}
					else//有右子树，但是第二次出现了，访问该结点
					{
						st1.pop();
						st.pop();
						num-=top.val;
					}
				}
				
			}
		}
		return false;
    }