小黑屋

0%

面试题-算法-二叉树遍历

发表于 更新于 分类于

二叉树遍历

先序遍历

先序遍历

点击看答案

递归方法：

1
2
3
4
5
6
7
8
9
10
11
void pre(BTreeNode treeNode){

    if(treeNode != null){
        //显示节点数据
        showNodeValue(treeNode);
        //先序遍历左子树
        pre(treeNode.left);
        //先序遍历右子树
        pre(treeNode.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
//非递归，手算的思想，先变访问边找，找到最左下方的，然后向上再向访问右边的
public static void iterativePreOrder(TreeNode p) {
    if (p == null) return;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while (!stack.empty() || p != null) {
        while (p != null) {
            visit(p);
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        p = p.right;
    }
}

//栈的思想，按层次倒着进栈，利用后进先出解决顺序问题
public static void iterativePreOrder_2(TreeNode p) {
    if (p == null) return;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(p);
    while (!stack.empty()) {
        p = stack.pop();
        visit(p);
        if (p.right != null) stack.push(p.right);
        if (p.left != null) stack.push(p.left);
    }
}

中序遍历

中序遍历

点击看答案

递归方法：

1
2
3
4
5
6
7
8
9
10
public static void middle(BTreeNode treeNode){
    if(treeNode != null){
        //中序遍历左子树
        middle(treeNode.left);
        //显示节点数据
        showNodeValue(treeNode);
        //中序遍历右子树
        middle(treeNode.right);
    }
}

非递归方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void iterativeInOrder(TreeNode p) {
    if (p == null) return;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    while (!stack.empty() || p != null) {
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        visit(p);
        p = p.right;
    }
}

后序遍历

后序遍历

点击看答案 递归方法： 
1
2
3
4
5
6
7
8
9
10
11
public static void behind(BTreeNode treeNode){
    if(treeNode != null){
        //后序遍历左子树
        behind(treeNode.left);
        //后序遍历右子树
        behind(treeNode.right);
        //显示节点数据
        showNodeValue(treeNode);
        
    }
}

非递归方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//双栈法，易于理解
public static void iterativePostOrder_3(TreeNode p) {
    if (p == null) return;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    Stack<TreeNode> result = new Stack<TreeNode>();
    while (!stack.empty() || p != null) {
        while (p != null) {
            stack.push(p);
            result.push(p);
            p = p.right;
        }
        if (!stack.empty()) p = stack.pop().left;
    }
    while (!result.empty()) {
        p = result.pop();
        visit(p);
    }
}

层次遍历

点击看答案 
1
2
3
4
5
6
7
8
9
10
11
public static void iterativeLevelOrder(TreeNode p) {
    if (p == null) return;
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(p);
    while (!queue.isEmpty()) {
        p = queue.poll();
        if (p.left != null) queue.offer(p.left);
        if (p.right != null) queue.offer(p.right);
        visit(p);
    }
}

以上内容可以参考这篇博客

谢谢你的鼓励