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)

將二叉樹近似認為是一棵左子樹右子樹節(jié)點數量分布均衡的樹，代入數值，通式結果為：2T(N/2)+O(1)；log(b,a) > d，所以時間復雜度為O(N)。
額外空間復雜度：
使用了額外的遞歸棧，最壞的情況：二叉樹退化為一個鏈表，所以額外空間復雜度為O(N)。

代碼執(zhí)行結果：

思路二：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)
代碼執(zhí)行結果：

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) ( 最差情況，當二叉樹退化為鏈表時)

執(zhí)行結果：

思路二：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)

執(zhí)行結果：