给你一个二叉树的根节点 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
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; }
