二叉树的遍历算法

发表于 分类于
学习笔记

翻译

traversal: 遍历
Binary Tree Traversal: 二叉树遍历

N:node L:left R:right

前序遍历(preorder): NLR

顺序展示: ABDECFG

图形走势

算法

1
2
3
4
5
6
7
public void preorder(TreeNode root) {
    if(root == null)
        return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

中序遍历(inorder)：LNR (Reverse inorder RNL )

顺序展示: DBEAFCG

图形走势

算法

1
2
3
4
5
6
7
public void inorder(TreeNode root) {
    if(root == null)
        return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}

后续遍历(postorder): LRN

顺序展示: DEBFGCA

算法

1
2
3
4
5
6
7
public void postorder(TreeNode root) {
    if(root == null)
        return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}

暴力破解: BFS brute force search （level by level)

顺序展示: ABCDEFG

时间复杂度: O(n)