算法

二叉树的几种遍历方式

Posted by xdshent on February 26, 2023

递归

  • 前序遍历

    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
28
29
30
31
32
33
34
35
36

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        preorder(result, root);
        return result;
    }
  
    private void preorder(List<Integer> result, TreeNode root){
        if(root == null){
            return;
        }
  
        result.add(root.val);
        preorder(result, root.left);
        preorder(result, root.right);
    }
}

  • 中序遍历

    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
28
29
30
31
32
33
34
35
36

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        inorder(result, root);
        return result;
    }
  
    private void inorder(List<Integer> result, TreeNode root){
        if(root == null){
            return;
        }
  
        inorder(result, root.left);
        result.add(root.val);
        inorder(result, root.right);
    }
}

  • 后序遍历

    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
28
29
30
31
32
33
34
35
36

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        postorder(result, root);
        return result;
    }
  
    private void postorder(List<Integer> result, TreeNode root){
        if(root == null){
            return;
        }
  
        postorder(result, root.left);
        postorder(result, root.right);
        result.add(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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                result.add(node.val);
                stack.push(node);
                node = node.left;
            }
  
            if(!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }
        }
        return result;
    }
}

  • 中序遍历

    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
  
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
  
            if(!stack.isEmpty()){
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }
  
        return result;
    }
}

  • 后序遍历

    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
  
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        TreeNode lastViewed = root;
  
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
  
            node = stack.peek();
            if(node.right == null || node.right == lastViewed){
                node = stack.pop();
                result.add(node.val);
                lastViewed = node;
                node = null;
            }else{
                node = node.right;
            }
        }
  
        return result;
    }
}
CATALOG
    FEATURED TAGS
    Java SpringCloud 算法
    FRIENDS