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

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

深度优先遍历

如下树的深度优先遍历结果为：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);
        }
    }