小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

二叉树求和问题

Posted on 2013-04-16 11:37 小明 阅读(2535) 评论(1)  编辑  收藏 所属分类: 数据结构和算法
问题给定一个二叉树，每个节点的值是一个数字（0-9），每个从根节点到叶节点均能组成一个数字。
比如如果从根节点到叶节点的路径是1-2-3，那么这代表了123这个数字。
求出所有这样从根节点到叶节点的数字之和。

比如，对于二叉树
  1
 /  \
2   3

一共有两条路径1->2和1->3，那么求和的结果就是12+13=25
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        //write code here
    }
}

分析：
此问题不难，主要是一个深度优先算法，使用了一个stringbuffer记录当前的路径，每次找到一个叶节点，就记下当前的值。当返回到上一层节点，注意要删除最后一次用来回朔。

代码如下：

public class SumTreeNodes {
    
    class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }
    
    StringBuffer current = new StringBuffer();
    int sum = 0;
    
    private void dfs(TreeNode node){
        int val = node.val;
        current.append(val+"");
        if(node.left==null && node.right==null){ //leaf here
            sum += Integer.parseInt(current.toString());
        }
        else{
            if(node.left!=null){
                dfs(node.left);
                current.setLength(current.length()-1);
            }
            if(node.right!=null){
                dfs(node.left);
                current.setLength(current.length()-1);
            }
        }
    }
    
     public int sumNumbers(TreeNode root) {
         sum = 0;
         current.setLength(0);
         if(root!=null){
             dfs(root);
         }
         return  sum;
     }
}








评论

# re: 二叉树求和问题[未登录]  回复  更多评论   

2013-04-17 11:08 by Harry
object TreeVisitor {
trait Monoid[A] {
def mempty: A
def mappend(a: A, b: A): A
}
implicit object IntMonoid extends Monoid[Int] {
def mempty = 0
def mappend(a: Int, b: Int) = a * 10 + b
}
implicit object StringMonoid extends Monoid[String]{
def mempty = ""
def mappend(a:String,b:String) = a+b
}

trait Tree[A]
case class TreeNode[A](n: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case class Leaf[A](num: A) extends Tree[A]

def visitTree[A: Monoid](t: Tree[A], path: A): List[A] = {
val ev = implicitly[Monoid[A]]
t match {
case TreeNode(n, left, right) =>
visitTree(left, ev.mappend(path, n)) ++ visitTree(right, ev.mappend(path, n))
case Leaf(num) => List(ev.mappend(path, num))
}
}
def main(args: Array[String]): Unit = {
val t1 = TreeNode(10, Leaf(7), Leaf(8))
val t2 = TreeNode(200, t1, Leaf(9))
val t3 = TreeNode(3000, t2, t2)
val t4 = TreeNode(40000, t3, t2)
val sumt = visitTree(t4,0).sum
println(sumt)
val s1 = TreeNode("1",Leaf("2"),Leaf("3"))
val s2 = TreeNode("2",s1,Leaf("4"))
val sums = visitTree(s2,"") map {x=>x.toInt}
println(sums.sum)


}

}

只有注册用户登录后才能发表评论。
网站导航: