【leetcode刷題】22.二叉樹的中序遍歷—

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

記憶：中序遍歷不忘“左鏈入堆疊”

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

今天作業中剛好遇到部門下拉樹，那就做一道中序遍歷吧！

Question

94. 二叉樹的中序遍歷

難度：簡單

給定一個二叉樹的根節點 root ，回傳它的中序遍歷，

示例 1：
輸入：root = [1,null,2,3]
輸出：[1,3,2]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
示例 4：
輸入：root = [1,2]
輸出：[2,1]
示例 5：
輸入：root = [1,null,2]
輸出：[1,2]
提示：

樹中節點數目在范圍 [0, 100] 內
-100 <= Node.val <= 100

進階: 遞回演算法很簡單，你可以通過迭代演算法完成嗎？

Solution

二叉樹的遍歷應該算是比較基本的內容，

首先分清什么是前序、中序、后序：

前序遍歷：列印 - 左 - 右
中序遍歷：左 - 列印 - 右
后序遍歷：左 - 右 - 列印

實作思路也很簡單，非常典型的遞回

終止條件：當前節點為空時
函式內：遞回的呼叫左節點，列印當前節點，再遞回呼叫右節點

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

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