leetcode94.二叉树的中序遍历
题目链接
二叉树的中序遍历：
对于这棵二叉树，中序遍历的结果为：
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;
}
}
时间复杂度分析：
通过master公式：
master公式：T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
将二叉树近似认为是一棵左子树右子树节点数量分布均衡的树，代入数值，通式结果为：2T(N/2)+O(1)；log(b,a) > d，所以时间复杂度为O(N)。
额外空间复杂度：
使用了额外的递归栈，最坏的情况：二叉树退化为一个链表，所以额外空间复杂度为O(N)。
代码执行结果：
思路二：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;
}
}
时间复杂度为：O(N),额外空间使用了stack,额外空间复杂度为O(N)
代码执行结果：
leetcode144.二叉树的前序遍历
二叉树的前序遍历：
对于这棵二叉树，前序遍历的结果为：
1,2,4,5,3,6,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> preorderTraversal(TreeNode root) {
if(root == null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
时间复杂度：O(N)；
额外空间复杂度：O(N) ( 最差情况，当二叉树退化为链表时)
执行结果：
思路二：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;
}
}
时间复杂度：O(N)
额外空间复杂度：O(N)
执行结果：
