二叉树的深度和广度优先遍历
二叉树的前序、中序和后序遍历大家可能已经手到擒来了,本文将带你学习二叉树的深度和广度优先遍历,以下是 C++ 代码:
深度优先遍历
/**
* 二叉树的深度优先遍历, 使用栈
* @param root
* @return
*/
std::list<int> dfs(TreeNode root){
std::stack stack;
std::list<int> list;
if(root==null)
return list;
//压入根节点
stack.push(root);
//然后就循环取出和压入节点,直到栈为空,结束循环
while (!stack.empty()){
TreeNode t=stack.top();
stack.pop();
if(t.right!=null)
stack.push(t.right);
if(t.left!=null)
stack.push(t.left);
list.push_back(t.val);
}
return list;
}
/**
* 递归解法
* @param root
* @return
*/
void solution(TreeNode root)
{
list<int> list;
depthTraversal(list,root);
}
void dfs(list<Integer> list,TreeNode tn)
{
if (tn!=null)
{
list.push_back(tn);
//每次先添加左节点,直到没有子节点点,返回上一级
dfs(tn.left);
dfs(tn.right);
}
}
广度优先遍历
/**
* 二叉树的广度优先遍历, 使用队列
* @param root
* @return
*/
std::ist<int> bfs(TreeNode root) {
std::queue<TreeNode> queue;
std::list<int> list;
if(root==null)
return list;
queue.push(root);
while (!queue.empty()){
TreeNode t=queue.front();
queue.pop();
if(t.left!=null)
queue.push(t.left);
if(t.right!=null)
queue.push(t.right);
list.push_back(t.val);
}
return list;
}