遍历方式

• 前序遍历
  • 根 左 右
• 中序遍历
  • 左 根 右
• 后续遍历
  • 左 右 根
• 深度优先遍历
  • 从根节点开始先遍历先遍历左子树在遍历右子树
• 广度优先遍历
  • 按层遍历

例子

这是一个二叉树

• 前序遍历
  1,3,4,2,5
• 中序遍历
  4,3,2,1,5
• 后序遍历
  4,2,3,5,1
• 广度优先遍历
  1,3,5,4,2
• 深度优先遍历
  1,3,4,2,5

实现

class Solution {
    List<Integer> preOrder = new ArrayList<>();
    List<Integer> inOrder = new ArrayList<>();
    List<Integer> postOrder = new ArrayList<>();

    // 前序遍历
    public void preOrder(TreeNode treeNode) {
        preOrder.add(treeNode.val);
        if (treeNode.left != null){
            preOrder(treeNode.left);
        }
        if (treeNode.right != null){
            preOrder(treeNode.right);
        }
    }

    // 中序遍历
    public void inOrder(TreeNode treeNode){
        if (treeNode.left != null){
            inOrder(treeNode.left);
        }
        inOrder.add(treeNode.val);
        if (treeNode.right != null){
            inOrder(treeNode.right);
        }
    }

    // 后序遍历
    public void postOrder(TreeNode treeNode){
        if (treeNode.left != null){
            postOrder(treeNode.left);
        }
        if (treeNode.right != null){
            postOrder(treeNode.right);
        }
        postOrder.add(treeNode.val);
    }

    // 广度优先搜索
    public List<Integer> bfs(TreeNode treeNode){
       List<Integer> bfs = new ArrayList<>();
       if (treeNode == null){
           return bfs;
       }
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(treeNode);
       while (!queue.isEmpty()){
           TreeNode t = queue.poll();
           bfs.add(t.val);
           if (t.left != null){
               queue.offer(t.left);
           }
           if (t.right != null){
               queue.offer(t.right);
           }
       }
       return bfs;
    }

    // 深度优先搜索
    public List<Integer> dfs(TreeNode treeNode){
        List<Integer> dfs = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        if (treeNode == null){
            return dfs;
        }
        while (!stack.isEmpty()){
            TreeNode t = stack.pop();
            dfs.add(t.val);
            //先让右结点入栈，在pop时确保左结点先出栈
            if (t.right != null){
                stack.push(t.right);
            }
            if (t.left != null){
                stack.push(t.left);
            }
        }
        return dfs;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode t = new TreeNode(1);
        t.left = new TreeNode(3);
        t.right = new TreeNode(5);
        t.left.left = new TreeNode(4);
        t.left.right = new TreeNode(2);
        solution.preOrder(t);
        solution.inOrder(t);
        solution.postOrder(t);
        System.err.println(solution.preOrder);
        System.err.println(solution.inOrder);
        System.err.println(solution.postOrder);
        System.err.println(solution.bfs(t));
        System.err.println(solution.dfs(t));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

• 输出

[1, 3, 4, 2, 5]
[4, 3, 2, 1, 5]
[4, 2, 3, 5, 1]
[1, 3, 5, 4, 2]
[1, 3, 4, 2, 5]