题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
112. 路径总和
解法1 递归
官方给的解答，非常清晰简明。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
//顺着节点下去，sum值要减去选取的节点的值
sum -= root.val;
//如果给的只有一个根节点，此时sum应该为0
if ((root.left == null) && (root.right == null))
return (sum == 0);
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
解法2 迭代
从根节点开始sum随路径向下减去相应的节点值，到达叶子结点时判断sum是否为0，是返回true，不是则去另一个叶子节点的路径。
不能单纯的在路径上每经过一个节点判断sum是否为0，因为sum在到达叶子节点的途中有可能会减为0，此时不能返回true。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
//申请两个栈，一个用来存节点，一个用来存sum随节点的变动
LinkedList<TreeNode> stack1 = new LinkedList<>();
LinkedList<Integer> stack2 = new LinkedList<>();
TreeNode curr = root;
while (!stack1.isEmpty() || curr != null) {
//从最左边的叶子节点开始，跳出while时，curr = null
while (curr != null) {
sum -= curr.val;
stack1.push(curr);
stack2.push(sum);
curr = curr.left;
}
//curr此时为叶子节点
curr = stack1.pop();
//必须是叶子节点才算，要满足这个节点左右孩子为null并且sum此时等于0
if (sum == 0 && curr.left == null && curr.right == null) {
return true;
}
sum = stack2.pop();
curr = curr.right;
}
return false;
}
}
题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
113. 路径总和Ⅱ
解法1 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list = new LinkedList<>();
LinkedList<Integer> res = new LinkedList<>();
pathSum(list, res, root, sum);
return list;
}
public void pathSum(List<List<Integer>> list, LinkedList<Integer> res, TreeNode root, int sum){
if(root == null){
return;
}
res.add(root.val);
if(root.val == sum && root.left == null && root.right == null){
list.add(new ArrayList<>(res));
}else{
pathSum(list, res, root.left, sum - root.val);
pathSum(list, res, root.right, sum - root.val);
}
//回溯
res.removeLast();
}
}
题目描述
给定一个二叉树，返回所有从根节点到叶子节点的路径。
257. 二叉树的所有路径
解法1 递归
最想想到递归。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
helper(root,"",res);
return res;
}
//res用来存储所有路径，path用来存放遍历到的路径
public void helper(TreeNode root, String path, List<String> res){
//root为null，直接跳出函数，返回的res为空
if(root != null){
path += Integer.toString(root.val);
//找到了根节点，将路径存入res中
if(root.left == null && root.right == null){
res.add(path);
root = null;
}else{
//不是根节点，添加"->"并继续遍历
path += "->";
helper(root.left,path,res);
helper(root.right,path,res);
}
}
}
}
题目描述
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
1022. 从根到叶的二叉树进制数之和
解法1
也可以用上面题的方法求出所有路径，再进行二进制数之和的计算。这里使用递归，边累加边遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumRootToLeaf(TreeNode root) {
return helper(root,0);
}
private int helper(TreeNode root, int sum){
if(root == null) return 0;
//sum等于从根节点到当前节点的二进制数的十进制表示
sum = 2 *sum + root.val;
//遇到叶子节点，返回sum，代表(又)一条路径的二进制数被累加
if(root.left == null && root.right == null){
return sum;
}
//没到叶子节点，继续遍历
return helper(root.left, sum) + helper(root.right, sum);
}
}
