树的广度优先遍历跟深度优先遍历

最近准备面试，刷刷应届生的基本算法.............

深度优先遍历

如下树的深度优先遍历结果为：A B D E C F G

 *     A*    / \*   B   C*  / \  /\* D  E F G

DFS实现

深度优先遍历分先序遍历、后序遍历、中序遍历
遍历顺序为先根节点、再左子树、再又子树
数据结构：栈
java实现逻辑

public void DFS(TreeNode root) {Stack<TreeNode> stack = new Stack<>();stack.add(root);while (!stack.isEmpty()) {// 移除最后一个TreeNode tempNode = stack.pop();System.out.println(tempNode.element);// 后进先出if (tempNode.right != null)stack.add(tempNode.right);if (tempNode.left != null)stack.add(tempNode.left);}}

广度优先遍历

如下树的广度优先遍历结果为：A B C D E F G

 *     A*    / \*   B   C*  / \  /\* D  E F G

BFS实现

数据结构：队列
java实现：

 public void BFS(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.add(root);// 先进先出while (!queue.isEmpty()) {TreeNode tempTreeNode = queue.remove();System.out.println(tempTreeNode.element);if (tempTreeNode.left != null)queue.add(tempTreeNode.left);if (tempTreeNode.right != null)queue.add(tempTreeNode.right);}}