package other.algorithm;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 
 */

public class TreeType {

    class TreeNode {
        TreeNode left;
        TreeNode right;
        Integer data;
    }

    /**
     * 前序非递归
     */
    public void preOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.empty()) {
            while (p != null) {
                System.out.println(p.data);
                stack.push(p);
                p = p.left;
            }
            if (!stack.empty()) {
                p = stack.pop();
                p = p.right;
            }
        }
    }

//    public void preOrder1(TreeNode root) {
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode p = root;
//        while (p != null || !stack.empty()) {
//            while (p != null) {
//                System.out.println(p.data);
//                stack.push(p);
//                p = p.left;
//            }
//            if (!stack.empty()) {
//                p = stack.pop();
//                p = p.right;
//            }
//        }
//    }

    /**
     * 中序非递归
     */
    public void midOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.empty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (!stack.empty()) {
                p = stack.pop();
                System.out.println(p.data);
                p = p.right;
            }
        }
    }

    /**
     * 后序非递归遍历
     * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，
     * 则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
     * 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，
     * 左孩子和右孩子都在根结点前面被访问。
     *
     * @param root
     */
    public void postOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        TreeNode pre = null;
        stack.push(p);
        while (!stack.empty()) {
            p = stack.peek();
            if ((p.left == pre || p.right == pre) || (p.left == null && p.right == null)) {
                System.out.println(p.data);
                stack.pop();
                pre = p;
            } else {
                if (p.right != null) {
                    stack.push(p.right);
                }
                if (p.left != null) {
                    stack.push(p.left);
                }
            }
        }
    }

    /**
     * 层次遍历
     * <p>
     * 增加两个Node：last和nlast
     * last：表示当前遍历层最右结点
     * nlast：表示下一层最右结点
     * 遍历时，每次将nlast指向插入队列元素，最后一个插入结点时即最右结点。插入左右孩子之后，检测last是否为当前输出结点，
     * 若是，则表示需要进行换行，并将last指向下一层的nlast。
     *
     * @param root
     */
    public void printTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode last = root;
        TreeNode nlast = root;
        while (!queue.isEmpty()) {
            TreeNode t = queue.peek();
            System.out.print(queue.poll().data + " ");
            if (t.left != null) {
                queue.add(t.left);
                nlast = t.left;
            }
            if (t.right != null) {
                queue.add(t.right);
                nlast = t.right;
            }
            // 如果当前输出结点是最右结点，那么换行
            if (last == t) {
                System.out.println();
                last = nlast;
            }
        }
    }


    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return null;
        List<List<Integer>> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> temp = new ArrayList<>();
        TreeNode cur = root;
        TreeNode next = root;
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.pop();
            temp.add(tmp.data);
            if (tmp.left != null) {
                queue.add(tmp.left);
                next = tmp.left;
            }
            if (tmp.right != null) {
                queue.add(tmp.right);
                next = tmp.right;
            }
            if (cur == tmp) {
                list.add(temp);
                temp = new ArrayList<>();
                cur = next;
            }
        }
        return list;
    }

    // 102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null) return list;
        queue.add(root);
        List<Integer> row = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 1; i <= size; i++) {  // 逐个输出队列内元素个数
                TreeNode p = queue.pop();
                row.add(p.data);
                if (p.left != null) {
                    queue.add(p.left);
                }
                if (p.right != null) {
                    queue.add(p.right);
                }
            }
            list.add(row);
            row = new ArrayList<>();
        }
        return list;
    }

    /**
     * 判断是对称二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return help(root, root);
    }

    private boolean help(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return (p.data.equals(q.data)) && help(p.left, q.right) && help(p.right, q.left);
    }

    /**
     * 最大深度
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;
        return Math.max(left, right);
    }

    /**
     * 是否为平衡二叉树
     *
     * @param root
     * @return
     */
    Boolean ret = true;

    public boolean isBalanced(TreeNode root) {
        depth(root);
        return ret;
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left) + 1;
        int right = depth(root.right) + 1;
        if (Math.abs(left - right) > 1) ret = false;
        return Math.max(left, right);
    }

    /**
     * 最小深度
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int ret = Integer.MAX_VALUE;
        if (root.left != null)
            ret = Math.min(minDepth(root.left), ret);
        if (root.right != null) {
            ret = Math.min(minDepth(root.right), ret);
        }
        return ret + 1;
    }

    // 100. 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return (p.data == q.data) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    // 112. 路径总和
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.data == sum;
        return hasPathSum(root.left, sum - root.data) || hasPathSum(root.right, sum - root.data);
    }


    // 113. 路径总和 II
    List<List<Integer>> ret2 = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret2;
    }

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.data);
        targetSum -= root.data;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret2.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }


    // 226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }

    void invert(TreeNode root) {
        if (root == null) return;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invert(root.left);
        invert(root.right);
    }

    // 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;
    }


    // 257. 二叉树的所有路径
    public void construct_paths(TreeNode root, String path, LinkedList<String> paths) {
        if (root != null) {
            path += Integer.toString(root.data);
            if ((root.left == null) && (root.right == null))  // 当前节点是叶子节点
                paths.add(path);  // 把路径加入到答案中
            else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root.left, path, paths);
                construct_paths(root.right, path, paths);
            }
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<String> paths = new LinkedList();
        construct_paths(root, "", paths);
        return paths;
    }


    // 404. 左叶子之和
    int res = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        dfs(root, false);
        return res;
    }

    private void dfs(TreeNode node, boolean isLeft) {
        if (node == null) return;
        if (node.left == null && node.right == null && isLeft) {
            res += node.data;
        }
        dfs(node.left, true);
        dfs(node.right, false);

    }
}