给你一个二叉树的根节点 root ，按
任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
输入：root = [1,2,3,null,5]
输出：[“1->2->5″,”1->3”]
public List<String> binaryTreePaths(TreeNode root) {
List<String> list=new ArrayList<>();
List<TreeNode> list1=new ArrayList<>();
if(root==null)
return null;
backtracking(list,list1,root);
return list;
}
public void backtracking(List<String> list,List<TreeNode> list1,TreeNode root){
list1.add(root);
TreeNode treeNode = list1.get(list1.size() - 1);
if(treeNode.left==null&&treeNode.right==null){
String s= String.valueOf(list1.get(0).val);
for(int i=1;i<list1.size();i++){
s=s.concat("->"+list1.get(i).val);
}
list.add(s);
return;
}
if(root.left!=null){
backtracking(list,list1,root.left);
list1.remove(list1.size()-1);
}
if(root.right!=null){
backtracking(list,list1,root.right);
list1.remove(list1.size()-1);
}
}给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。叶子节点 是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
public boolean hasPathSum(TreeNode root, int targetSum) {
List<List<TreeNode>> list=new ArrayList<>();
List<TreeNode> list1=new ArrayList<>();
if(root==null)
return false;
backtracking(list,list1,root,targetSum);
if(list.size()==0)
return false;
return true;
}
public void backtracking(List<List<TreeNode>> list,List<TreeNode> list1,TreeNode root,int targetSum){
list1.add(root);
int sum = list1.stream().mapToInt(i -> i.val).sum();
TreeNode treeNode = list1.get(list1.size() - 1);
if(treeNode.left==null&&treeNode.right==null){
if(sum==targetSum){
list.add(new ArrayList<>(list1));
return;
}
else
return;
}
if(root.left!=null){
backtracking(list,list1,root.left,targetSum);
list1.remove(list1.size()-1);
}
if(root.right!=null){
backtracking(list,list1,root.right,targetSum);
list1.remove(list1.size()-1);
}
}给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
输入：root = [1,2], p = 1, q = 2
输出：1来源：力扣（LeetCode）
链接：
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null; if(root==p||root==q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(right!=null&&left!=null) return root; else if(right==null&&left!=null) return left; else if(left==null&&right!=null) return right; else return null; }版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/143057.html