- it技术
- Java实现求二叉树路径总和
标题：Java实现求二叉树路径总和
public class TestPathSum02 {
public boolean pathSum(TreeNode p
, int target
) {
if(p
== null
) {
return false;
}
Queue
<TreeNode> q
= new LinkedList<>();
q
.offer(p
);
while(!q
.isEmpty()) {
int size
= q
.size();
for(int i
= 0; i
< size
; i
++) {
TreeNode node
= q
.poll();
if(node
.left
!= null
) {
node
.left
.val
+= node
.val
;
q
.offer(node
.left
);
}
if(node
.right
!= null
) {
node
.right
.val
+= node
.val
;
q
.offer(node
.right
);
}
if(node
.left
== null
&& node
.right
== null
) {
if(node
.val
== target
) {
return true;
}
}
}
}
return false;
}
public boolean pathSum02(TreeNode p
, int target
, int sum
) {
if(p
== null
) {
return false;
}else {
boolean res1
= this.pathSum02(p
.left
, target
, sum
+ p
.val
);
boolean res2
= this.pathSum02(p
.right
, target
, sum
+ p
.val
);
if(p
.left
== null
&& p
.right
== null
) {
if(sum
+ p
.val
== target
) {
return true;
}
}
if(res1
|| res2
) {
return true;
}
return false;
}
}
public TreeNode
initTree(Integer
[] a
) {
if(a
== null
|| a
.length
== 0) {
return null
;
}
int t
= 0;
TreeNode p
= new TreeNode(a
[t
]);
Queue
<TreeNode> q
= new LinkedList<>();
q
.offer(p
);
while(!q
.isEmpty()) {
TreeNode node
= q
.poll();
if(t
+ 1 == a
.length
) {
return p
;
}else {
t
++;
if(a
[t
] == null
) {
node
.left
= null
;
}else {
node
.left
= new TreeNode(a
[t
]);
q
.offer(node
.left
);
}
}
if(t
+ 1 == a
.length
) {
return p
;
}else {
t
++;
if(a
[t
] != null
){
node
.right
= new TreeNode(a
[t
]);
q
.offer(node
.right
);
}
}
}
return p
;
}
@Test
public void test() {
System
.out
.println("使用init的");
Integer
[] a
= new Integer[] {1, 2};
TreeNode p
= this.initTree(a
);
System
.out
.println("使用递归");
System
.out
.println("isTrue:" + this.pathSum02(p
, 2, 0));
}
}
