binary-tree

二叉树

前序遍历 (Preorder Traversal)

按根左右的顺序遍历

迭代

需要用到一个栈辅助，先push右节点

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

    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);

    while (!stack.empty()) {
        TreeNode tmp = (TreeNode)stack.pop();
        result.add(tmp.val);

        if (tmp.right != null) stack.push(tmp.right); // !important
        if (tmp.left != null) stack.push(tmp.left);
    }

    return result;
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 public void dfs(TreeNode root, List<Integer> list) {
    if (root != null) {
        list.add(root.val);
        dfs(root.left, list);
        dfs(root.right, list);
    }
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;

    dfs(root, list);
    return list;
}

中序遍历 (Inorder Traversal)

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
public void inorder(TreeNode root, List<Integer> list) {
    if(root != null) {
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();

while (true) {
    while(root != null) {
        stack.push(root);
        root = root.left;
    }

    if (stack.empty()){
        break;
    }

    TreeNode tmp = stack.pop();
    result.add(tmp.val);
    root = tmp.right;
}

return result;
}

后序遍历 (Postorder Traversal)

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
 public void inorder(TreeNode root, List<Integer> list) {
    if(root != null) {
        inorder(root.left, list);
        inorder(root.right, list);
        list.add(root.val);
    }
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while(!stack.empty()) {
        TreeNode tmp = stack.pop();
        result.add(tmp.val);
        if (tmp.left != null) stack.push(tmp.left);
        if (tmp.right != null) stack.push(tmp.right);
    }

    Collections.reverse(result);
    return result;
}

层序遍历 (Level-order traversal)

广度优先搜索(breadth-first search)就是用的层序遍历

需要借助一个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (queue.peek() != null) {
        List<Integer> result = new ArrayList<Integer>();
        int len = queue.size();
        while (len-- > 0) {
            TreeNode tmp = queue.poll();  
            result.add(tmp.val);
            if (tmp.left != null) queue.offer(tmp.left);
            if (tmp.right != null) queue.offer(tmp.right);
        }
        results.add(result);
    }

    return results;
}

###