前言
哈喽，大家好，我是一條。
糊塗算法，難得糊塗
今天工作中剛好遇到部門下拉樹，那就做一道中序周遊吧！
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);
}
} Result
複雜度分析
- 時間複雜度：O(N)
🌈尋寶
⭐今天是堅持刷題更文的第22/100天
⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力
⭐更多算法題歡迎關注專欄《leetcode》
為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等
怎麼領取請大家自己找，尋寶遊戲現在開始。
找不到可以評論留言，一條就會注意到你。
如果還不行，請私信我。
