二叉树的遍历：前序，中序和后序遍历(Tree Traversal Algorithms: PreOrder, InOrder and PostOrder)

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.7k 阅读时长 ≈ 5 分钟

By Frank Luo

The Tree Traversal Algorithms are used to traversal the tree including Binary Tree and N-ary Tree.

  1. Binary Tree Traversal

94. Binary Tree Inorder Traversal 144. Binary Tree Preorder Traversal 145. Binary Tree Postorder Traversal

  1. N-ary Tree Traversal

589. N-ary Tree Preorder Traversal 590. N-ary Tree Postorder Traversal

Binary Tree

PreOrder

Algorithm Preorder(tree) 1. Visit the root; 2. Traverse the left subtree, i.e., call Preorder(left-subtree); 3. Traverse the right subtree, i.e., call Preorder(right-subtree).

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    preOrder(root, ans);
    return ans;
}

public void preOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    list.add(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            ans.add(root.val);
            root = root.left;
        }
        
        root = stack.pop();
        root = root.right;
    }
    
    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

InOrder

Algorithm Inorder(tree)

  1. Traverse the left subtree, i.e., call Inorder(left-subtree);
  2. Visit the root;
  3. Traverse the right subtree, i.e., call Inorder(right-subtree).

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal_rec(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    inOrder(root, ans);
    return ans;
}

public void inOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    if (root.left != null) {
        inOrder(root.left, list);
    }
    list.add(root.val);
    if (root.right != null) {
        inOrder(root.right, list);
    }
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        
        root = stack.pop();
        ans.add(root.val);
        root = root.right;
    }
    
    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

PostOrder

Algorithm Postorder(tree) 1. Traverse the left subtree, i.e., call Postorder(left-subtree); 2. Traverse the right subtree, i.e., call Postorder(right-subtree); 3. Visit the root.

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> postorderTraversal_rec(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    postOrder(root, ans);
    return ans;
}

public void postOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    postOrder(root.left, list);
    postOrder(root.right, list);
    list.add(root.val);
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    
    TreeNode prev = null;
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        if (root.right == null || root.right == prev) {
            ans.add(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

N-ary Tree Traversal

PreOrder

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    preOrderTraversal(root, ans);
    return ans;
}

public void preOrderTraversal(Node root, List<Integer> list) {
    if (root == null) {
        return;
    }
    list.add(root.val);
    List<Node> children = root.children;
    for (Node child : children) {
        preOrderTraversal(child, list);
    }
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> preorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node node = stack.pop();
        ans.add(node.val);
        List<Node> children = node.children;
        int size = children.size();
        for (int i = size - 1; i >= 0; i--) {
            stack.push(children.get(i));
        }
    }
    
    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

PostOrder

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorder_rec(Node root) {
    List<Integer> ans = new ArrayList<>();
    postOrderTraversal(root, ans);
    return ans;
}

public void postOrderTraversal(Node root, List<Integer> list) {
    if (root == null) {
        return;
    }
    List<Node> children = root.children;
    for (Node child : children) {
        postOrderTraversal(child, list);
    }
    list.add(root.val);
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> postorder(Node root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node node = stack.pop();
        ans.add(node.val);
        List<Node> children = node.children;
        int size = children.size();
        for (int i = 0; i < size; i++) {
            stack.push(children.get(i));
        }
    }
    
    Collections.reverse(ans);
    return ans;
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗