leetcode94.二叉树的中序遍历,144.二叉树的前序遍历

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)

执行结果：