對于下圖所示的二叉樹

其先序、中序、后序遍歷的序列如下：

• 先序遍歷： A、B、D、F、G、C、E、H
• 中序遍歷： B、F、D、G、A、C、E、H
• 后序遍歷： F、G、D、B、H、E、C、A
• 層序遍歷： A、B、C、D、E、F、G、H

/**
 * 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;
 *     }
 * }
 */

前序遍歷

先序遍歷操作程序：

若二叉樹為空，則空操作，否則依次執行如下3個操作

1. 訪問根結點；
2. 按先序遍歷左子樹；
3. 按先序遍歷右子樹，

遞回法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        preorder(root, list);
        return list;
    }
    public void preorder(TreeNode root, List<Integer> list){
        if (root == null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }
}

迭代法

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.peek();
            list.add(stack.pop().val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return list;
    }
}

中序遍歷

中序遍歷操作程序：

若二叉樹為空，則空操作，否則依次執行如下3個操作

1. 按中序遍歷左子樹；
2. 訪問根結點；
3. 按中序遍歷右子樹，

遞回法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        return list;
    }
    public void inorder(TreeNode root, List<Integer> list){
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

迭代法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode node =  root;
        while (node != null || !stack.isEmpty()){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else{
                node = stack.peek();
                list.add(stack.pop().val);
                node = node.right;
            }
        }
        return list;
    }
}

后序遍歷

后序遍歷操作程序：

若二叉樹為空，則空操作，否則依次執行如下3個操作：

1. 按后序遍歷左子樹；
2. 按后序遍歷右子樹；
3. 訪問根結點，

遞回法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        postorder(root, list);
        return list;
    }
    public void postorder(TreeNode root, List<Integer> list){
        if (root == null) return;
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }
}

迭代法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null; // 記錄上一個輸出的結點
        while (root != null || !stack.isEmpty()){
            while (root != null) { // 從當前結點向“左下”遍歷，找到位于“左下”方的結點
                stack.push(root);
                root = root.left;
            }
						// 定位到沒有左子樹的結點，接著準備處理右邊（要彈出是因為如果有右子樹，是要先讓右子樹進堆疊的）
            root = stack.pop(); 
						/*因為通過剛才的遍歷知道不存在左子樹了，現在開始向右走，下面的操作都是在沒有左子樹的前提下進行的*/
						/*將當前結點值輸出的條件是：【當前結點沒有右子樹】 或 【右子樹的值已經輸出過輪到當前結點了】*/
            if (root.right == null || root.right == prev) {
                list.add(root.val); // 將當前結點的值輸出
                prev = root; // 用prev記錄輸出的結點
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    } 
}

如果有左子樹，就一直走下去；如果有右子樹，則往右子樹走一步，再一直往左走下去，

層序遍歷

層序遍歷，又稱廣度優先遍歷，

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        
        if(root != null) queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            list.add(tmp);
// 若要回傳其節點值自底向上的層序遍歷，只需反轉得到的list即可
// Collections.reverse(list);
        }
        return list;
    }
}

標籤：其他

上一篇：Activiti7+SpringBoot

下一篇：分數與小數