leetcode94.二叉樹(shù)的中序遍歷
題目鏈接
二叉樹(shù)的中序遍歷：
對(duì)于這棵二叉樹(shù)弹渔，中序遍歷的結(jié)果為：
4,2,5,1,6,3,7
思路一：recursion
代碼如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null){
return list;
}else{
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
}
return list;
}
}
時(shí)間復(fù)雜度分析：
通過(guò)master公式：
master公式：T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 復(fù)雜度為O(N^log(b,a))
2) log(b,a) = d -> 復(fù)雜度為O(N^d * logN)
3) log(b,a) < d -> 復(fù)雜度為O(N^d)
將二叉樹(shù)近似認(rèn)為是一棵左子樹(shù)右子樹(shù)節(jié)點(diǎn)數(shù)量分布均衡的樹(shù)揖铜，代入數(shù)值，通式結(jié)果為：2T(N/2)+O(1)；log(b,a) > d，所以時(shí)間復(fù)雜度為O(N)然遏。
額外空間復(fù)雜度：
使用了額外的遞歸棧，最壞的情況：二叉樹(shù)退化為一個(gè)鏈表吧彪，所以額外空間復(fù)雜度為O(N)待侵。
代碼執(zhí)行結(jié)果：
思路二：stack
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
if(root != null){
stack.push(root);
root = root.left;
}else{
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
}
時(shí)間復(fù)雜度為：O(N),額外空間使用了stack,額外空間復(fù)雜度為O(N)
代碼執(zhí)行結(jié)果：
leetcode144.二叉樹(shù)的前序遍歷
二叉樹(shù)的前序遍歷：
對(duì)于這棵二叉樹(shù)，前序遍歷的結(jié)果為：
1,2,4,5,3,6,7
前序遍歷比中序遍歷還要簡(jiǎn)單那么一丟丟姨裸，不寫(xiě)解析了直接上代碼秧倾。
思路一：recursion
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
時(shí)間復(fù)雜度：O(N)；
額外空間復(fù)雜度：O(N) ( 最差情況傀缩，當(dāng)二叉樹(shù)退化為鏈表時(shí))
執(zhí)行結(jié)果：
思路二：stack
代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root != null){
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
if(root.right != null){
stack.push(root.right);
}
if(root.left != null){
stack.push(root.left);
}
}
}
return list;
}
}
時(shí)間復(fù)雜度：O(N)
額外空間復(fù)雜度：O(N)
執(zhí)行結(jié)果：
