中序遍歷二叉樹
題目：
- 給定一個二叉樹的根節(jié)點root掷伙，返回它的中序遍歷結(jié)果
示例.png
解法：
- 第一種方法（遞歸）：中序遍歷是指：左子樹—根節(jié)點—右子樹宝冕，可以定義一個中序遍歷的函數(shù)祝谚，然后遞歸調(diào)用
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
inorder(root,res);//調(diào)用遞歸的方法
return res;
}
public static void inorder(TreeNode root,List<Integer> res){
if(root==null){//如果傳進來的根節(jié)點為空谜洽，說明這是空樹
return;
}
inorder(root.left,res);//遍歷左子樹
res.add(root.val);//遍歷完左子樹后恳不，將根節(jié)點添加到數(shù)組中
inorder(root.right,res);//遍歷右子樹
}
}
時間復雜度為O(n)需要遍歷二叉樹的所有結(jié)點
空間復雜度為O(n)遞歸調(diào)用需要用到棧先來存儲元素
- 第二種方法（迭代）：跟第一種方法等價悍抑，迭代是把棧模擬出來
class Solution { public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> stk=new Stack<>();//創(chuàng)建一個棧
while(root!=null||!stk.isEmpty()){
while(root!=null){
stk.push(root);
root=root.left;//遍歷左子樹鳄炉，然后將節(jié)點進棧
}
root=stk.pop();//左子樹為空，然后將棧頂元素出棧為當前節(jié)點
res.add(root.val);
root=root.right;//遍歷當前節(jié)點的右子樹
}
return res;
}
}
