图文详解深度优先，广度优先遍历

public class Solution {
    private static class Node {
        /**
         * 节点值
         */
        public int value;
        /**
         * 左节点
         */
        public Node left;
        /**
         * 右节点
         */
        public Node right;
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    public static void dfs(Node treeNode) {
        if (treeNode == null) {
            return;
        }
        // 遍历节点
        process(treeNode)
        // 遍历左节点
        dfs(treeNode.left);
        // 遍历右节点
        dfs(treeNode.right);
    }
}
复制代码

/**
 * 使用栈来实现 dfs
 * @param root
 */
public static void dfsWithStack(Node root) {
    if (root == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while (!stack.isEmpty()) {
        Node treeNode = stack.pop();
        // 遍历节点
        process(treeNode)
        // 先压右节点
        if (treeNode.right != null) {
            stack.push(treeNode.right);
        }
        // 再压左节点
        if (treeNode.left != null) {
            stack.push(treeNode.left);
        }
    }
}
复制代码

/**
 * 使用队列实现 bfs
 * @param root
 */
private static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        Node node = stack.poll();
        System.out.println("value = " + node.value);
        Node left = node.left;
        if (left != null) {
            stack.add(left);
        }
        Node right = node.right;
        if (right != null) {
            stack.add(right);
        }
    }
}
复制代码

3
   / \
  9  20
    /  \
   15   7
复制代码

/**
 * leetcode 104: 求树的最大深度
 * @param node
 * @return
 */
public static int getMaxDepth(Node node) {
    if (node == null) {
        return 0;
    }
    int leftDepth = getMaxDepth(node.left) + 1;
    int rightDepth = getMaxDepth(node.right) + 1;
    return Math.max(leftDepth, rightDepth);
}
/**
 * leetcode 111: 求树的最小深度
 * @param node
 * @return
 */
public static int getMinDepth(Node node) {
    if (node == null) {
        return 0;
    }
    int leftDepth = getMinDepth(node.left) + 1;
    int rightDepth = getMinDepth(node.right) + 1;
    return Math.min(leftDepth, rightDepth);
}
复制代码

3
   / \
  9  20
    /  \
   15   7
复制代码

[
  [3],
  [9,20],
  [15,7]
]
复制代码

/**
 * leetcdoe 102: 二叉树的层序遍历, 使用 bfs
 * @param root
 */
private static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) {
    if (root == null) {
        // 根节点为空，说明二叉树不存在，直接返回空数组
        return Arrays.asList();
    }
    // 最终的层序遍历结果
    List<List<Integer>> result = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 记录每一层
        List<Integer> level = new ArrayList<>();
        int levelNum = queue.size();
        // 遍历当前层的节点
        for (int i = 0; i < levelNum; i++) {
            Node node = queue.poll();
            // 队首节点的左右孩子入队,由于 levelNum 是在入队前算的，所以入队的左右节点并不会在当前层被遍历到
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            level.add(node.value);
        }
        result.add(level);
    }
    return result;
}
复制代码

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []  #嵌套列表，保存最终结果
        if root is None:
            return res
        from collections import deque
        que = deque([root])  #队列，保存待处理的节点
        while len(que)!=0:
            lev = []  #列表，保存该层的节点的值
            thislevel = len(que)  #该层节点个数
            while thislevel!=0:
                head = que.popleft()  #弹出队首节点
                #队首节点的左右孩子入队
                if head.left is not None:
                    que.append(head.left)
                if head.right is not None:
                    que.append(head.right)
                lev.append(head.val)  #队首节点的值压入本层
                thislevel-=1
            res.append(lev)
        return res
复制代码

private static final List<List<Integer>> TRAVERSAL_LIST  = new ArrayList<>();
/**
 * leetcdoe 102: 二叉树的层序遍历, 使用 dfs
 * @param root
 * @return
 */
private static void dfs(Node root, int level) {
    if (root == null) {
        return;
    }
    if (TRAVERSAL_LIST.size() < level + 1) {
        TRAVERSAL_LIST.add(new ArrayList<>());
    }
    List<Integer> levelList = TRAVERSAL_LIST.get(level);
    levelList.add(root.value);
    // 遍历左结点
    dfs(root.left, level + 1);
    // 遍历右结点
    dfs(root.right, level + 1);
}
复制代码