剑指34:
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。
从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
class Solution { /* 广度优先遍历 回溯 注意为负数的情况!! */ public List<List<Integer>> pathSum(TreeNode root, int target) { List<List<Integer>> resList = new LinkedList<>(); if(root == null){ return resList; } List<Integer> path = new LinkedList<>(); path.add(root.val); search(root,root.val,target,path,resList); return resList; } public void search(TreeNode node, int curSum, int target, List<Integer> path, List<List<Integer>> resList){ if(node == null){ return; } if(node.left==null && node.right==null){ if(curSum == target) { resList.add(new LinkedList(path)); } // 如果路径有负数就不用return return; } // if(curSum>target){ // // 如果路径有负数就不用return // return; // } // 搜左 if(node.left!=null) { path.add(node.left.val); search(node.left, curSum + node.left.val, target, path, resList); path.remove(path.size() - 1); } // 搜右 if(node.right!=null) { path.add(node.right.val); search(node.right, curSum + node.right.val, target, path, resList); path.remove(path.size() - 1); } } }
网易笔试:
返回从根节点到某个节点(可以是非叶子节点)路径,取最短路径,最左路径
public class Wangyi_exam1 { // 输入一个二叉树,以及目标长度des。[1,2,3,4,5] 找到从根到某个节点的和等于该长度的路径 // 若有多条路径,取最短路径,若有长度相同取最左边那条路径 public static void main(String[] args) { // Scanner scanner = new Scanner(System.in); // String s1 = scanner.nextLine(); // int des = Integer.parseInt(scanner.nextLine()); // 输入字符串 String s1 = "[3,1,4,2,4,4,1]"; int des = 8; // 输出应该为[3,5] String[] strs = s1.substring(1,s1.length()-1).split(","); int[] tree = new int[strs.length]; for (int i = 0; i < tree.length; i++) { if(strs[i]!="null") { tree[i] = Integer.parseInt(strs[i]); }else { tree[i] = -1; } } // 回溯寻找路径 // 定义一个当前路径pathList,每次除非遇到路径更短的否则不会更新。避免左右顺序问题。 // 定义一个bestPath shortLength = strs.length;路径不可能超过树的长度。 // 定义一个当前路径总和 cur_sum path.add(tree[0]); findMinPath(0,0,des,tree); System.out.print(bestPath.toString()); } static List<Integer> path = new ArrayList<>(); static List<Integer> bestPath = null; public static void findMinPath(int t, int cur_sum, int des, int[] tree){ // 找到头了 注:边界条件,中间节点为null if(t>=tree.length || tree[t]==-1){ return; } cur_sum += tree[t]; if(cur_sum == des){ // 找到的话 判断是否需要更新 if(bestPath==null || path.size()<bestPath.size()){ // 更新bestPath bestPath = new ArrayList<>(path); } return; }else if(cur_sum > des){ // 超过了返回 return; }else{ //继续往左往右找 注:判断是否越界 if(findLeft(t)<tree.length && tree[findLeft(t)]!=-1 ) { path.add(tree[findLeft(t)]); findMinPath(findLeft(t), cur_sum, des, tree); path.remove(path.size() - 1); } if(findRight(t)<tree.length && tree[findRight(t)]!=-1 ) { path.add(tree[findRight(t)]); findMinPath(findRight(t), cur_sum, des, tree); path.remove(path.size() - 1); } } } /** * 返回左子树index */ public static int findLeft(int index){ return index*2+1; } /** * 返回右子树index */ public static int findRight(int index){ return index*2+2; } }