iT邦幫忙

2024 iThome 鐵人賽

DAY 7
0
佛心分享-刷題不只是刷題

Java刷題A:Leetcode Top 100 Liked系列 第 7

Day7 Binary Tree二元樹 - 題目2:94. Binary Tree Inorder Traversal

  • 分享至 

  • xImage
  •  

原文題目
Given the root of a binary tree, return the inorder traversal of its nodes' values.

題目摘要

  1. 問題描述: 給定一個二元樹的根節點,要求返回其節點值的中序遍歷順序。
  2. 輸入: 二元樹的根節點TreeNode root
  3. 輸出: 包含節點值的列表,按中序遍歷順序排列。

Example 1:
https://ithelp.ithome.com.tw/upload/images/20240919/20168780iwInjGPglw.png

Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:

Example 2:
https://ithelp.ithome.com.tw/upload/images/20240919/20168780u40eFHGKTr.png

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

解題思路一

  1. 理解中序走訪的順序:

    中序走訪順序是「左子樹 -> 根節點 -> 右子樹」。

  2. 使用堆疊儲存節點:

    我們將當前節點(從根節點開始)儲存到堆疊中,並不斷向左子樹走訪直到遇到 null。每遇到一個非空節點,我們將它推入堆疊。

  3. 處理當前節點:

    當左子樹走訪到底後(即 currentNode == null),從堆疊中彈出節點,將該節點的值加入結果列表中,然後移動到右子樹。

  4. 重複過程:

    重複以上過程,直到所有節點都被處理完,即堆疊為空且當前節點為 null

  5. 回傳結果:

    最後返回包含節點值的列表,即中序走訪的結果。

程式碼一

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

        //while(!(currentNode==null&&stack.isEmpty)){}一樣意思寫法
        while(currentNode != null || !stack.isEmpty()){
            //左子樹先一路走到底
            while(currentNode != null){
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //當左子樹到底時將最後一個進stack的節點移至結果陣列儲存再往右子樹開始找
            currentNode = stack.pop();
            result.add(currentNode.val);
            currentNode = currentNode.right;
        }
        return result;
    }
}

解題思路二

  1. 創建結果列表

    使用一個列表 result 來存儲中序走訪的結果,即按照「左子樹 → 根節點 → 右子樹」的順序除去節點值。

  2. 開始中序走訪

    使用輔助方法 makeInorder 來遞迴地遍歷樹的每個節點,並將遍歷結果添加到結果列表中。

  3. 處理空節點

    當節點為 null 時,直接返回,因為空節點不需要進一步處理。

  4. 遞迴遍歷左子樹、處理當前節點及遞迴遍歷右子樹

    • 遞迴使用 makeInorder 方法遍歷左子樹。
    • 遍歷完左子樹後,將當前節點的值添加到結果列表中。
    • 遞迴調用 makeInorder 方法遍歷右子樹。
  5. 回傳結果列表:

    遍歷完成後,返回結果列表 result

    對左子樹和右子樹重複相同的步驟,直到走訪完所有節點。

程式碼二

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //設立一個列表來存儲中序走訪的結果
        List<Integer> result = new ArrayList<>();

        makeInorder(root, result); //開始中序走訪
        return result; //走訪完成則回傳結果列表       
    }

    private void makeInorder(TreeNode node, List<Integer> result) {
        //如果當前節點為null則返回
        if (node == null) {
            return;
        }
        makeInorder(node.left, result); //遞迴遍歷左子樹
        result.add(node.val); //直到不能再遍歷左子樹,將當前節點的值加到結果列表中
        makeInorder(node.right, result); //遞迴遍歷右子樹
    }    
}

結論
這題我和我的組員分別使用了兩種解法,第一種是迭代解法,第二種則是遞迴解法。迭代解法利用堆疊有效地處理了樹的深度,避免了遞迴可能帶來的空間消耗。遞迴解法透過輔助函數來簡化整個過程,使程式碼更為清晰易懂。藉由練習這題題目不僅讓我加深了對二元樹中序遍歷的理解,也透過小組討論讓我認識了不同解法及其特點。


上一篇
Day6 Binary Tree二元樹 - 題目1:226. Invert Binary Tree
下一篇
Day8 Binary Tree二元樹 - 題目3:105. Construct Binary Tree from Preorder and Inorder Traversal
系列文
Java刷題A:Leetcode Top 100 Liked26
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言