深度优先搜索思想:
本节学习深度优先搜索算法的核心思想和一般方法.
深度优先搜索算法的一般方法:
深度优先搜索算法的一个常用应用场景是利用递归与非递归方法实现二叉树的前序遍历(前序遍历即在访问节点的过程中,对于该二叉树及其所有子树,均先访问根节点,再访问左子树,最后访问右子树)
1.递归方式:
递归就是函数自身调用自身.用递归的方式实现二叉树的前序遍历,对于任何一棵二叉树想实现前序遍历,就要先访问根节点,再对其左子节点执行同样过程,最后对其右节点执行同样过程.由于每个节点只访问一次,因此采用递归的时间复杂程度为O(n)
2.非递归方式:
用非递归方式实现深度优先算法前序遍历二叉树就需要借助一种常用的数据结构--栈,栈先进后厨的特点发挥很大的作用.先将根节点入栈,然后进行一个迭代的过程,只要栈不为空,就弹出栈顶部元素进行输出,继而使右节点入栈,最后左子节点入栈,如此一来,由于栈先进后出的特点,因此其可以实现先遍历左子树再遍历右子树,即二叉树的前序遍历完成.