自有网站建设的团队,遂宁市建设局网站,制作一个app软件需要多少时间,用自己主机做网站问题描述#xff1a;给定一个二叉树#xff0c;返回所有从根节点到叶子节点的路径。说明#xff1a;叶子节点是指没有子节点的节点。
DFS求解#xff1a;定义一个全局的链表#xff0c;用来装所有的结果#xff0c;通过DFS遍历#xff0c;一旦遍历到当前节点没有子节点…问题描述给定一个二叉树返回所有从根节点到叶子节点的路径。说明叶子节点是指没有子节点的节点。
DFS求解定义一个全局的链表用来装所有的结果通过DFS遍历一旦遍历到当前节点没有子节点则将该节点加入链表后放入全局链表中如果当前节点有两个子节点则新生成一个从父节点传下来的链表并进行两个分支的递归求解。
public void dfs(TreeNode root,ListTreeNodelist,ListListTreeNoderes)
{
if(root.leftnullroot.rightnull)
{
list.add(root);
res.add(list);
return;
}else if(root.left!nullroot.rightnull)
{
list.add(root);
dfs(root.left,list,res);
}else if(root.right!nullroot.leftnull)
{
list.add(root);
dfs(root.right,list,res);
}else
{
list.add(root);
ListTreeNodelist1new LinkedList(list);
dfs(root.left,list,res);
dfs(root.left,list1,res);
}
}
public ListListTreeNodeDfs(TreeNode root)
{
ListListTreeNoderesnew ListListTreeNode();
ListTreeNodelistnewLinkedList();
dfs(root,list,res);
return res;
}
BFS求解
public ListListTreeNodebfs(TreeNode root)
{
QueueTreeNodequeuenew LinkedList();
QueueListTreeNodequeueListnew Linkedlits();
ListTreeNodelistnew LinkedLits();
list.add(root);
queue.add(root);
queueList.add(list)
while(!queue.isEmpty())
{
ListTreeNodetempListqueueList.poll();
TreeNode tempNodequeue.poll();
if(tempNode.leftnulltempNode.rightnull)
{
res.add(tempList);
}else if(tempNode.left!nulltempNode.rightnull)
{
tempList.add(tempNode.left);
queue.add(tempNode.left);
}else if(tempNode.right!nulltempNode.leftnull)
{
tempList.add(tempNode.right);
queue.add(tempNode.right);
}else
{
ListTreeNodenewList1new LinkedList(tempList);
tempList.add(tempNode.left);
queueList.add(tempList);
newList1.add(tempNode.right);
queuelist.add(newList1);
}
}
return res;
}
