leetcode_129_Sum Root to Leaf Numbers

描述：

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   /   2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

思路：

代码：

public int sumNumbers(TreeNode root) {
		if (root == null)
			return 0;
		int temp=0,sum=0;
		LinkedList<TreeNode>linkedList=new LinkedList<TreeNode>();
		Stack<TreeNode> st1 = new Stack<TreeNode>();
		linkedList.addLast(root);
		TreeNode top = null;
		while (!linkedList.isEmpty()) {
			top=linkedList.getLast();
			while(top.left!=null)//达到页结点
			{
				linkedList.addLast(top.left);
				top=top.left;
			}
			while(!linkedList.isEmpty())
			{
				top=linkedList.getLast();
				if(top.right==null)//无右子树时，访问结点
				{
					if(top.left==null)
					{
						temp=0;
						for(int i=0;i<linkedList.size();i++)
							temp=temp*10+linkedList.get(i).val;
						sum+=temp;
					}
					linkedList.removeLast();
				}else 
				{
					if(st1.empty()||(!st1.empty()&&st1.peek()!=top))//有右子树且第一次出现，将右子树入栈，并将结点在st1中标记一下
					{
						st1.push(top);
						linkedList.addLast(top.right);
						break;//右子树入栈了，然后从右子树开始
					}
					else//有右子树，但是第二次出现了，访问该结点
					{
						st1.pop();
						linkedList.removeLast();
					}
				}
				
			}
		}
		return sum;
    }

结果：

leetcode_129_Sum Root to Leaf Numbers

原文：http://blog.csdn.net/mnmlist/article/details/44655401