文档章节

BrinaryTreePathSumToTarget

writeademo
 writeademo
发布于 2017/08/15 17:39
字数 256
阅读 4
收藏 0

 

Binary Tree的一个基本题。

 

遍历到底,比较sum vs. target。

注意divide的情况。要把遍历的例子写写。

LeetCode: Path Sum II

```

       /*

       Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

      

       A valid path is from root node to any of the leaf nodes.

      

       Example

       Given a binary tree, and target = 5:

      

       1

       / \

       2 4

       / \

       2 3

       return

      

       [

       [1, 2, 2],

       [1, 4]

       ]

       Tags Expand

       Binary Tree Binary Tree Traversal

       */

      

       /*

       Thoughts:

       path: has to be from root to leaf.

       binary tree: no order logic in the tree.

       DPS on all nodes. If final sum == target, add list of nodes into rst

       */

 

 

 

 

 

public class Solution {

public class TreeNode {

              public int val;

              public TreeNode left, right;

 

              public TreeNode(int val) {

                     this.val = val;

                     this.left = this.right = null;

              }

       }

    /**

     * @param root the root of binary tree

     * @param target an integer

     * @return all valid paths

     */

    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {

    List<List<Integer>> rst = new ArrayList<List<Integer>>();

              if (root == null) {

                     return rst;

              }

              dfs(rst, new ArrayList<Integer>(), root, 0, target);

              return rst;

       }

 

       private void dfs(List<List<Integer>> rst, ArrayList<Integer> list, TreeNode root, int add, int sum) {

              list.add(root.val);

              if (root.left == null && root.right == null) {

                     if (add + root.val == sum) {

                            rst.add(new ArrayList<Integer>(list));

                     }

                     return;

              }

              if (root.left != null) {

                     dfs(rst, list, root.left, add + root.val, sum);

                     list.remove(list.size() - 1);

              }

              if (root.right != null) {

                     dfs(rst, list, root.right, add + root.val, sum);

                     list.remove(list.size() - 1);

              }

       }

 

}

© 著作权归作者所有

writeademo
粉丝 26
博文 670
码字总数 250499
作品 0
东城
私信 提问

暂无文章

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部