一、題目大意
給定一個二叉樹的根節點 root ，回傳 它的 中序 遍歷 ，
示例 1：
輸入：root = [1,null,2,3]
輸出：[1,3,2]
示例 2：
輸入：root = []
輸出：[]
示例 3：
輸入：root = [1]
輸出：[1]
提示：
-
樹中節點數目在范圍 [0, 100] 內
-
-100 <= Node.val <= 100
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/binary-tree-inorder-traversal
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
二叉樹的中序遍歷順序為左 根 右，可以用遞回和非遞回來解，遞回解法十分直接，對左了節點呼叫遞回函式，根節點訪問值，右子節點再呼叫遞回函式，
非遞回有兩種方法，一種使用堆疊：從根節點開始，先將根節點壓入堆疊，然后再將其所有左節點壓入堆疊，然后取出堆疊頂節點，保存節點值，再將當前指標移到其右子節點上，若存在右子節點，則在下次回圈時又可將其所有左子節點壓入堆疊中，這樣就保證了訪問順序為左 根 右，
三、解題方法
3.1 Java實作 - 遞回實作
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traverse(list, root);
return list;
}
public void traverse(List<Integer> list, TreeNode root) {
if (root == null) {
return;
}
traverse(list, root.left);
list.add(root.val);
traverse(list, root.right);
}
}
四、總結小記
- 2022/10/8 節后活有點多呀
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511073.html
標籤：其他
上一篇：冒泡排序演算法并調優