自顶向下
一般路径
List<String> res=new ArrayList<String>();
public void printPath(TreeNode root,String s){
if(root==null){
return;
}
s+=(char)('a'+root.val);
if(root.left==null&&root.right==null){
res.add(s);
s.remove(s.size()-1);
return;
}
printPath(root.left,s);
printPath(root.right,s);
s.remove(s.size()-1);//相对于c++回溯,引用
}
应用一
class Solution {
PriorityQueue<String> queue=new PriorityQueue<String>((a,b)->a.compareTo(b));
public String smallestFromLeaf(TreeNode root) {
dfs(root,"");
return queue.peek();
}
public void dfs(TreeNode root,String s){
if(root==null){
return;
}
s+=(char)('a'+root.val);
if(root.left==null&&root.right==null){
queue.offer(new StringBuilder(s).reverse().toString());
s=s.substring(0,s.length()-1);
return;
}
dfs(root.left,s);
dfs(root.right,s);
s=s.substring(0,s.length()-1);
}
}
应用二
二叉树中的伪回文路径
伪回文路径最多有一个元素出现奇数次,将所有的元素进行次数异或运算
class Solution {
int res=0;
public int pseudoPalindromicPaths (TreeNode root) {
dfs(root,0);
return res;
}
public void dfs(TreeNode root,int cur){
if(root==null){
return ;
}
cur^=(1<<root.val);
if(root.left==null&&root.right==null){
if(cur==0||(cur&-cur)==cur){
res++;
}
}
dfs(root.left,cur);
dfs(root.right,cur);
}
}
给定和路径
List<List<Integer>> res=new ArrayList<List<Integer>>();
public voif dfs(TreeNode root,int sum,List<Integer> path){
if(root==null){
return;
}
sum-=root.val;
path.add(root.val);
if(root.left==null&&root.right==null&&sum==0){
res.add(new ArrayList<>(path));
path.remove(path.size()-1);
return;
}
dfs(root.left,sum,path);
dfs(root.right,sum,path);
sum+=root.val;
path.remove(path.size()-1);
}
非自顶向下
一般路径
class Solution {
int res=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
public int dfs(TreeNode root){
if(root==null){
return 0;
}
int left=dfs(root.left);
int right=dfs(root.right);
//将对应的节点值与0进行比较
left=Math.max(left,0);
right=Math.max(right,0);
res=Math.max(res,left+right+root.val);
return Math.max(left,right)+root.val;
}
}