1.二叉樹的遍歷

二叉樹主要有兩種遍歷方式：

深度優先遍歷：先往深走，遇到葉子節點再往回走，

前序遍歷（遞回法，迭代法）中左右
中序遍歷（遞回法，迭代法）左中右
后序遍歷（遞回法，迭代法）左右中

廣度優先遍歷：一層一層的去遍歷，

層次遍歷（迭代法）

對比圖可以理解一下遍歷的程序，前中后序遍歷涉及遞回和迭代兩種方法講解，

2.LeetCode鏈接

前序遍歷：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/

中序遍歷：https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/

后序遍歷：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/

層序遍歷：https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/

感興趣的可以去練練手！！！

3.前序遍歷

前序遍歷的順序是中左右，即先根節點、左子樹、右子樹，那么我們先考慮遞回進行求解，

要列印出前序遍歷節點的數值，所以引數里需要放節點的數值，除了這一點就不需要在處理什么資料了也不需要有回傳值，所以遞回函式回傳型別就是void，

　　 Traversal(TreeNode root, List<Integer> list)

當前遍歷的節點是空了，那么本層遞回就要要結束了，所以如果當前遍歷的這個節點是空，就直接return，

if (cur == NULL) return;

前序遍歷是中左右的循序，所以在單層遞回的邏輯，是要先取中節點的數值，

list.add(root.val);

Traversal(root.left, list);

Traversal(root.right, list);

所以總體的遞回代碼如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

對于迭代法，難度會更大一點！！！

前序遍歷是中左右，每次先處理的是中間節點，那么先將根節點放入堆疊中，然后將右孩子加入堆疊，再加入左孩子，為什么要先加入右孩子，再加入左孩子呢？因為這樣出堆疊的時候才是中左右的順序，

所以我們不難寫出代碼如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

4.中序遍歷

中序遍歷的順序是左中右，即先左子樹、根節點、右子樹，那么我們先考慮遞回進行求解，

　　思路和上面一樣，唯一的區別就是變了順序，所以總體的遞回代碼如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        preorder(root.left, result);
        result.add(root.val);   //注意
        preorder(root.right, result);
    }
}

　　對于迭代法，難度會更大一點！！！

　　中序遍歷是左中右，但是代碼和上面有一些不同，中序遍歷是左中右，先訪問的是二叉樹頂部的節點，然后一層一層向下訪問，直到到達樹左面的最底部，再開始處理節點（也就是在把節點的數值放進result陣列中），這就造成了處理順序和訪問順序是不一致的，在使用迭代法寫中序遍歷，就需要借用指標的遍歷來幫助訪問節點，堆疊則用來處理節點上的元素，

　　所以我們可以寫出代碼如下：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

5.后序遍歷

　　后序遍歷的順序是左右中，即先左子樹、右子樹、根節點，那么我們先考慮遞回進行求解，

　　思路和上面一樣，唯一的區別就是變了順序，所以總體的遞回代碼如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        preorder(root.left, result);
        preorder(root.right, result);
        result.add(root.val);   //注意
    }
}

　　對于迭代法，會前序遍歷難度會小一點！！！

　　先序遍歷是中左右，后續遍歷是左右中，那么我們只需要調整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉result陣列，輸出的結果順序就是左右中了，如下圖：

　　所以我們可以很快的寫出代碼如下：

class Solution {
    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.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

　　注意，這里主要是入堆疊順序變了，變成先左后右！！！

6.層序遍歷

層序遍歷一個二叉樹，就是從左到右一層一層的去遍歷二叉樹，這種遍歷的方式和我們之前講過的都不太一樣，

需要借用一個輔助資料結構即佇列來實作，佇列先進先出，符合一層一層遍歷的邏輯，而是用堆疊先進后出適合模擬深度優先遍歷也就是遞回的邏輯，

了解了思路，我們可以很快的寫出層序遍歷的代碼：

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun02(root);
        return resList;
    }
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();
            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }
            resList.add(itemList);
        }
    }
}

　　主要就是建立一個佇列，依次對出佇列的數的左右子樹入隊，同時記錄下當前佇列的大小，這樣可以每一次得到一層的數，

　　怎么樣，看完以后是不是簡單多了，當然得有一點點這個方面基礎，不然看起來還是有點費勁！！！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540142.html

標籤：其他

上一篇：「貪心」構成特定和需要添加的最少元素(力扣第1785題)

下一篇：大角度非迭代的空間坐標旋轉C#實作