119 BFS和DFS解二叉树的所有路径

问题描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。说明：叶子节点是指没有子节点的节点。

DFS求解：定义一个全局的链表，用来装所有的结果，通过DFS遍历，一旦遍历到当前节点没有子节点，则将该节点加入链表后放入全局链表中，如果当前节点有两个子节点，则新生成一个从父节点传下来的链表，并进行两个分支的递归求解。

public void dfs(TreeNode root,List<TreeNode>list,List<List<TreeNode>>res)
{
if(root.left==null&&root.right==null)
{
list.add(root);
res.add(list);
return;
}else if(root.left!=null&&root.right==null)
{
list.add(root);
dfs(root.left,list,res);
}else if(root.right!=null&&root.left==null)
{
list.add(root);
dfs(root.right,list,res);
}else
{
list.add(root);
List<TreeNode>list1=new LinkedList(list);
dfs(root.left,list,res);
dfs(root.left,list1,res);
}
}
public List<List<TreeNode>>Dfs(TreeNode root)
{
List<List<TreeNode>>res=new List<List<TreeNode>>();
List<TreeNode>list=newLinkedList<>();
dfs(root,list,res);
​​​​​​​return res;
}

BFS求解：

public List<List<TreeNode>>bfs(TreeNode root)
{
Queue<TreeNode>queue=new LinkedList<>();
Queue<List<TreeNode>>queueList=new Linkedlits<>();
List<TreeNode>list=new LinkedLits<>();
list.add(root);
queue.add(root);
queueList.add(list)
while(!queue.isEmpty())
{
List<TreeNode>tempList=queueList.poll();
TreeNode tempNode=queue.poll();
if(tempNode.left==null&&tempNode.right==null)
{
res.add(tempList);
}else if(tempNode.left!=null&&tempNode.right==null)
{
tempList.add(tempNode.left);
queue.add(tempNode.left);
}else if(tempNode.right!=null&&tempNode.left==null)
{
tempList.add(tempNode.right);
queue.add(tempNode.right);
}else
{
List<TreeNode>newList1=new LinkedList<>(tempList);
tempList.add(tempNode.left);
queueList.add(tempList);
newList1.add(tempNode.right);
queuelist.add(newList1);
}
}
return res;
}