Java二叉树路径和代码示例
给定一个二叉树,找出所有路径中各节点相加总和等于给定目标值的路径。
一个有效的路径,指的是从根节点到叶节点的路径。
样例
给定一个二叉树,和目标值=5:
1 /\ 24 /\ 23
返回:
[ [1,2,2], [1,4] ]
代码如下:
/** *DefinitionofTreeNode: *publicclassTreeNode{ *publicintval; *publicTreeNodeleft,right; *publicTreeNode(intval){ *this.val=val; *this.left=this.right=null; *} *} */ publicclassSolution{ /** *@paramroottherootofbinarytree *@paramtargetaninteger *@returnallvalidpaths */ publicList>binaryTreePathSum(TreeNoderoot,inttarget){ //Writeyourcodehere returndfs(root,newArrayList
(),0,newArrayList >(),target); } publicList
>dfs(TreeNoderoot,List
node,intsum,List >paths,inttarget) { if(root==null) { returnnewArrayList
>(); } List
>path=newArrayList
>(); if(root.left!=null) { List
nodes=newArrayList (); if(node!=null) { nodes.addAll(node); } nodes.add(root.val); List >temp=dfs(root.left,nodes,sum+root.val,paths,target); if(temp!=null) { path.addAll(temp); } } if(root.right!=null) { List
nodes=newArrayList (); if(node!=null) { nodes.addAll(node); } nodes.add(root.val); List >temp=dfs(root.right,nodes,sum+root.val,paths,target); if(temp!=null) { path.addAll(temp); } } if(root.left==null&&root.right==null) { List
nodes=newArrayList (); if(node!=null) { nodes.addAll(node); } nodes.add(root.val); if(sum+root.val==target) { path.add(nodes); }else{ path=newArrayList >(); } } returnpath; } }
referance
java编程求二叉树最大路径问题代码分析
java中继承测试代码分析
总结
以上就是本文关于Java二叉树路径和代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!