[数据结构与算法]LeetCode-树

94：二叉树的中序遍历

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return list;
    }
    private void dfs(TreeNode cur){
        if(cur == null){
            return;
        }
        dfs(cur.left);
        list.add(cur.val);
        dfs(cur.right);
    }
}

95：不同的二叉搜索树II

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0){
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> list = new LinkedList<>();
        if(start > end){
            list.add(null);
            return list;
        }
        // 回溯法（令根节点值为i）
        for(int i = start; i <= end; i++){
            //所有可行的左子树集合
            List<TreeNode> leftLists = generateTrees(start, i - 1);
            //所有可行的右子树集合
            List<TreeNode> rightLists = generateTrees(i + 1, end);
            for(TreeNode left : leftLists){
                for(TreeNode right : rightLists){
                    TreeNode cur = new TreeNode(i);
                    cur.left = left;
                    cur.right = right;
                    list.add(cur);
                }
            }
        }
        return list;
    }
}

96：不同的二叉搜索树

class Solution {
    //结果是对的，但是会超出时间限制
    public int numTrees(int n) {
        if(n == 0){
            return 1;
        }
        List<TreeNode> list = generateTrees(1, n);
        return list.size();
    }
    private List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> res = new LinkedList<>();
        if(start > end){
            res.add(null);
            return res;
        } 
        for(int i = start; i <= end; i++){
            List<TreeNode> leftList = generateTrees(start, i - 1);
            List<TreeNode> rightList = generateTrees(i + 1, end);
            for(TreeNode left : leftList){
                for(TreeNode right : rightList){
                    TreeNode cur = new TreeNode();
                    cur.left = left;
                    cur.right = right;
                    res.add(cur);
                }
            }
        }
        return res;
    }
}

class Solution {
    // 动态规划
    public int numTrees(int n) {
        // 下表是？，就代表？个元素可构成的二叉树总数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        // i是根节点
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                // i左边的二叉树数量*右边的二叉树数量
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

98：验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    private boolean isValidBST(TreeNode root, Integer max, Integer min){
        if(root == null){
            return true;
        }
        int val = root.val;
        // min != null必须放前面
        if(min != null && val <= min){
            return false;
        }
        // max != null必须放前面
        if(max != null && val >= max){
            return false;
        }
        if(!isValidBST(root.left, val, min)){
            return false;
        }
        if(!isValidBST(root.right, max, val)){
            return false;
        }
        return true;
    }
}

99：恢复二叉搜索树

100：相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null && q != null){
            return false;
        }
        if(q == null && p != null){
            return false;
        }
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

101：对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }
    private boolean isSymmetric(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null && right != null){
            return false;
        }
        if(right == null && left != null){
            return false;
        }
        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

102：二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // LinkedList<TreeNode> ll =  new LinkedList<>();
        Queue<TreeNode> ll =  new LinkedList<>();
        if(root == null){
            return res;
        }
        // ll.add(root);
        ll.offer(root);
        while(!ll.isEmpty()){
            int len = ll.size();
            for(int i = 0; i < len; i++){
                // TreeNode temp = ll.removeFirst();
                TreeNode temp = ll.poll();
                if(temp.left != null){
                    // ll.add(temp.left);
                    ll.offer(temp.left);
                }
                if(temp.right != null){
                    // ll.add(temp.right);
                    ll.offer(temp.right);
                }
                path.add(temp.val);
            }
            if(!path.isEmpty()){
                res.add(new ArrayList<>(path));
                path.clear();
            }
        }
        return res;
    }
}

103：二叉树的锯齿形层序遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        // 变了
        LinkedList<Integer> path = new LinkedList<>();
        // LinkedList<TreeNode> ll =  new LinkedList<>();
        Queue<TreeNode> ll =  new LinkedList<>();
        if(root == null){
            return res;
        }
        // ll.add(root);
        ll.offer(root);
        // 变了
        boolean right2left = true;
        while(!ll.isEmpty()){
            int len = ll.size();
            for(int i = 0; i < len; i++){
                // TreeNode temp = ll.removeFirst();
                TreeNode temp = ll.poll();
                if(temp.left != null){
                    // ll.add(temp.left);
                    ll.offer(temp.left);
                }
                if(temp.right != null){
                    // ll.add(temp.right);
                    ll.offer(temp.right);
                }
                if(right2left){
                    path.addLast(temp.val);
                }else{
                    path.addFirst(temp.val);
                }
            }
            if(!path.isEmpty()){
                res.add(new ArrayList<>(path));
                path.clear();
                right2left = !right2left;
            }
        }
        return res;
    }
}

104：二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

105：从前序和中序构造二叉树

106：从中序和后序构造二叉树

107：二叉树的层序遍历II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        LinkedList<Integer> path = new LinkedList<>();
        LinkedList<TreeNode> ll =  new LinkedList<>();
        // Queue<TreeNode> ll =  new LinkedList<>();
        ll.addLast(root);
        // ll.offer(root);
        while(!ll.isEmpty()){
            int len = ll.size();
            for(int i = 0; i < len; i++){
                TreeNode temp = ll.removeFirst();
                // TreeNode temp = ll.poll();
                if(temp.left != null){
                    ll.addLast(temp.left);
                    // ll.offer(temp.left);
                }
                if(temp.right != null){
                    ll.addLast(temp.right);
                    // ll.offer(temp.right);
                }
                path.addLast(temp.val);
            }
            if(!path.isEmpty()){
                res.addFirst(new ArrayList<>(path));
                path.clear();
            }
        }
        return res;
    }
}

108：将有序数组转换为二叉搜索树

109：有序链表转换二叉搜索树

110：平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return Math.abs(left - right) > 1 ? false : true && isBalanced(root.left) && isBalanced(root.right);
    }
    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        return left > right ? left + 1 : right + 1;
    }
}

111：二叉树的最小深度

112：路径总和

113：路径总和II

114：二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        while(root != null){
            TreeNode left = root.left;
            TreeNode right = root.right;
            if(left != null){
                TreeNode tem = left;
                while(tem.right != null){
                    tem = tem.right;
                }
                tem.right = right;
                root.right = left;
                root.left = null;
            }
            root = root.right;
        }
    }
}

116：填充每个节点的写一个右侧节点指针

117：填充每个节点的写一个右侧节点指针II

124：二叉树中的最大路径和

class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root);
        return max;
    }
    private int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftLen = dfs(root.left);
        if(leftLen < 0){
            leftLen = 0;
        }
        int rightLen = dfs(root.right);
        if(rightLen < 0){
            rightLen = 0;
        }
        int sum = root.val + leftLen + rightLen;
        if(sum > max){
            max = sum;
        }
        return root.val + Math.max(leftLen, rightLen);
    }
}

129：求根节点到叶节点数字之和

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode root, int sum){
        if(root == null){
            return 0;
        }
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }
        return dfs(root.left, sum) + dfs(root.right, sum);
    }
}

144：二叉树的前序遍历

145：二叉树的后序遍历