二叉树遍历

Posted on Edited on In Waline:

本文讲述二叉树遍历的方式, 分别分为前序、中序、后序, 其中每种采用递归和非递归的方式实现.

####0x01. 前序遍历

  • 递归的方式
1
2
3
4
5
6
7
public static void recursionPreorderTraversal(TreeNode root){
    if (root != null){
        System.out.print(root.val + " ");
        recursionPreorderTraversal(root.left);
        recursionPreorderTraversal(root.right);
    }
}
  • 非递归的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void preorderTraversal(TreeNode root) {
    // 用来暂存节点的栈
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    // 游标节点
    TreeNode node = root;
    
    while(node != null && !treeNodeStack.isEmpty()){
        while(node != null) {
            System.out.print(node.val + " ");
            treeNodeStack.push(node);
            node = node.left;
        }
        if (!treeNodeStack.isEmpty()){
            node = treeNodeStack.pop();
            node = node.right;
        }
    }
}

0x02.中序遍历

  • 递归的方式
1
2
3
4
5
6
7
public static void recursionMiddleorderTraversal(TreeNode root){
    if (root != null){
        recursionMiddleorderTraversal(root.left);
        recursionMiddleorderTraversal(root.val + " ");
        recursionMiddleorderTraversal(root.right);
    }
}
  • 非递归的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void middleorderTraversal(TreeNode root){
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    while (node != null || !treeNodeStack.isEmpty()){
        while(node != null){
            treeNodeStack.push(node);
            node = node.left;
        }
        if (!treeNOdeStack.isEmpty()) {
            node = treeNodeStack.pop();
            System.out.print(node.val + " ");
            node = node.right;
        }
    }
}

0x03. 后序遍历

  • 递归的方式
1
2
3
4
5
6
7
public static void recursionPostorderTraversal(TreeNode root){
    if (root != null){
        recursionPostorderTraversal(root.left);
        recursionPostorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}
  • 非递归的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void postorderTraversal(TreeNode root){
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;
    TreeNode lastVisit = root;

    while (node != null || !treeNodeStack.isEmpty()){
        while(node != null){
            treeNodeStack.push(node);
            node = node.left;
        }
        // 查看当前的元素
        node = treeNodeStack.peek();
        // 如果右子树为空, 或者右子树已经访问, 则直接打印当前节点的值
        if (node.right == null || node.right == lastVisit){
            System.out.print(node.val + " ");
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        }else{
            // 否则继续遍历右子树
            node = node.right;
        }
    }
}