題目描述：給定一個二叉樹，返回它的中序 遍歷。示例: 輸入: [1,null,2,3] 1 \ 2 / 3輸出: [1,3,2] 解法一：遞歸（較簡單） /** * Definition for a binary tree node. * public class TreeNode { * int ...
題目描述：給定一個二叉樹，返回它的中序 遍歷。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
解法一：遞歸（較簡單）
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<Integer> lis = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if(root == null) return lis; //若節點為空，則返回當前結果數組 inorderTraversal(root.left); //對左子樹進行中序遍歷 lis.add(root.val); inorderTraversal(root.right); //對右子樹進行中序遍歷 return lis; } } 解法二：（迭代）--基於棧的中序遍歷 class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); 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(); list.add(cur.val); cur = cur.right; } } return list; } }
