package top100.top二叉树;

import top100.TreeNode;

import java.util.*;

public class TOP {
    //94. 二叉树的中序遍历
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return res;
    }
    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            res.add(root.val);
            inorder(root.right);
        }
    }


    //104. 二叉树的最大深度
    int maxDepth = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return maxDepth;
        }
        dfsMaxDepth(root, 0);
        return maxDepth;
    }
    private void dfsMaxDepth(TreeNode root, int res) {
        if (root == null) {
            maxDepth = Math.max(maxDepth, res);
        } else {
            dfsMaxDepth(root.left, res + 1);
            dfsMaxDepth(root.right, res + 1);
        }
    }


    //226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    //101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        } else {
            return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
        }
    }


    //543. 二叉树的直径
    int diameterOfBinaryTree = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfsDiameterOfBinaryTree(root);
        return diameterOfBinaryTree;
    }
    //计算当前节点到其叶子节点的最长距离
    private int dfsDiameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        //左右节点的最长距离
        int l = dfsDiameterOfBinaryTree(root.left);
        int r = dfsDiameterOfBinaryTree(root.right);
        diameterOfBinaryTree = Math.max(diameterOfBinaryTree, l + r);
        return Math.max(l, r) + 1;
    }


    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }


    //108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        int start = 0, mid = (nums.length - 1) / 2;
        TreeNode root = new TreeNode(nums[mid]); //二叉搜索树的根节点是中序遍历数组中间的数
        if (mid - start > 0) { //如果数组可以构成左子树
            root.left = sortedArrayToBST(Arrays.copyOfRange(nums, start, mid));
        }
        if (mid < nums.length - 1) { //如果数组可以构成右子树
            root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
        }
        return root;
    }


    //98. 验证二叉搜索树
    long preVal = Long.MIN_VALUE; //为了通过测试用例，设置比int最小还要小的值
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        //先判断左子树是否满足
        if (!isValidBST(root.left)) {
            return false;
        }
        //中序是否满足递增
        if (root.val <= preVal) {
            return false;
        }
        preVal = root.val; //更新pre值
        //判断又子树
        return isValidBST(root.right);
    }


    //230. 二叉搜索树中第K小的元素
    int res1;
    int k;
    ArrayList<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inOrder(root, k);
        return res1;
    }
    //中序遍历,从最小结点开始遍历:二叉搜索树的中序遍历为递增序列
    private void inOrder(TreeNode root, int k) {
        if (root == null) return;
        if (root.left != null) {
            inOrder(root.left, k);
        }
        list.add(root.val);
        if (list.size() == k) {
            res1 = root.val;
            return;
        }
        if (root.right != null) {
            inOrder(root.right, k);
        }
    }
    //230. 二叉搜索树中第K小的元素
    int res1;
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inOrder(root);
        return res1;
    }
    private void inOrder(TreeNode root) {
        if (root == null) return;
        //先递归到左端点
        inOrder(root.left);
        if (k == 0) return;
        //遍历到第k个
        if (--k == 0) res1 = root.val;
        //中序遍历
        inOrder(root.right);
    }


    //199. 二叉树的右视图
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                if (i == n - 1) {
                    res.add(cur.val);
                }
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
        }
        return res;
    }


    //114. 二叉树展开为链表
    //方法1：逆前序遍历
    TreeNode preTreeNode = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = preTreeNode;
        preTreeNode = root;
    }
    //方法2：前序遍历后重组
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        preOder(root, list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode pre = list.get(i - 1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
    private void preOder(TreeNode root, ArrayList<TreeNode> list) {
        if (root != null) {
            list.add(root);
            if (root.left != null) {
                preOder(root.left, list);
            }
            if (root.right != null) {
                preOder(root.right, list);
            }
        }
    }


    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        //获取根节点在中序的位置
        int mid = 0;
        for (int i = 0; i < n; i++) {
            if (inorder[i] == preorder[0]) {
                mid = i;
                break;
            }
        }
        //构造左右子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
        root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
        return root;
    }


    //437. 路径总和 III
    int res4 = 0;
    //从每个节点dfs
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        //遍历每个节点 bfs
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                dfs4(cur, targetSum);
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
        }
        return res4;
    }
    private void dfs4(TreeNode root, long curSum) {
        if (root != null) {
            curSum -= root.val;
            if (curSum == 0) {
                res4++;
            }
            //递归
            dfs4(root.left, curSum);
            dfs4(root.right, curSum);
        }
    }


    //236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }


    //124. 二叉树中的最大路径和
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs6(root);
        return res;
    }
    //计算root作为父结点所在在路径的最大路径和
    private int dfs6(TreeNode root) {
        if (root == null) return 0;
        //计算左子树的最大路径和,抛弃负数的路径
        int left = Math.max(0, dfs6(root.left));
        int right = Math.max(0, dfs6(root.right));
        //计算路径 left -> root -> right 的和
        res = Math.max(res, left + right + root.val);
        //返回root结点所在的子树最大路径和给父结点使用
        return root.val + Math.max(left, right);
    }
}