• 前序遍历（递归法，迭代法）：先根节点，再左右节点；
• 中序遍历（递归法，迭代法）：先左节点，再根节点，最后右节点；
• 后序遍历（递归法，迭代法）：先左右节点，再根节点。

• 层次遍历（迭代法）

class Solution {
    //前序遍历：中左右
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rslt=new ArrayList<>();
        traversal(root,rslt);
        return rslt;
    }

    //确定返回值
    public void traversal(TreeNode cur,List<Integer> rslt){
        //确定终止条件
        if(cur==null){
            return;
        }
        //确定每次递归的逻辑
        //中即当前节点，把当前节点输出
        rslt.add(cur.val);
        //左
        traversal(cur.left,rslt);
        //右
        traversal(cur.right,rslt);
    }
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> rslt=new ArrayList<Integer>();
    if(root==null){
        return rslt;
    }
    Deque<TreeNode> stack=new ArrayDeque<>();
    //★当栈为空且节点为空时遍历结束，root可以看做当前节点
    while(!stack.isEmpty()||root!=null){
        //中左
        while(root!=null){
            rslt.add(root.val);
            stack.push(root);
            root=root.left;
        }
        //右
        root=stack.pop();
        root=root.right;
    }
    return rslt;
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> rslt=new ArrayList<Integer>();
    traversal(root,rslt);
    return rslt;
}
public void traversal(TreeNode cur,List<Integer> rslt) {
    if(cur==null) return;
    traversal(cur.left,rslt);
    rslt.add(cur.val);
    traversal(cur.right,rslt);
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> rslt=new ArrayList<Integer>();
    if(root==null){
        return rslt;
    }
    Deque<TreeNode> stack=new ArrayDeque<>();
    //★当栈为空且节点为空时遍历结束，root可以看做当前节点
    while(!stack.isEmpty()||root!=null){
        //中左
        while(root!=null){
            rslt.add(root.val);
            stack.push(root);
            root=root.left;
        }
        //右——从栈里弹出来的元素一定是根节点和左子树访问完了的，接下来轮到右子树了
        root=stack.pop();
        root=root.right;
    }
    return rslt;
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> rslt=new ArrayList<Integer>();
    traversal(root,rslt);
    return rslt;
}
public void traversal(TreeNode cur,List<Integer> rslt){
    if(cur==null) return;
    //后序遍历——左右中
    traversal(cur.left,rslt);
    traversal(cur.right,rslt);
    rslt.add(cur.val);
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> rslt=new ArrayList<Integer>();
    if(root==null) return rslt;
    Deque<TreeNode> stack=new ArrayDeque<>();
    //用来记录历史访问记录
    TreeNode pre=null;
    while(!stack.isEmpty()||root!=null){
        //访问左子树
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
        root=stack.pop();
        //如果root的右子树为空，或者右子树访问完了(root.right==pre)，输出中
        if(root.right==null||root.right==pre){
            rslt.add(root.val);
            //★更新历史访问记录，在下一个循环中，pre代表上一个访问的节点
            pre=root;
            //★一颗子树的左右中都访问完了，该回到上一个父节点(已入栈)，把root置空这样下次循环就能拿到栈顶元素的上一个父节点了。
            root=null;
        }else{
            //如果root右子树不为空，访问右子树
            //★访问右节点前要把当前节点再次入栈！！！因为访问完右还要访问中
            stack.push(root);
            root=root.right;
        }
    }
    return rslt;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> rslt=new ArrayList<List<Integer>>();
    if(root==null) return rslt;
    Deque<TreeNode> queue=new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        //记录队列长度，遍历时用来控制每层访问几个元素
        int size=queue.size();
        List<Integer> level=new ArrayList<>();
        while(size>0){
            root=queue.poll();
            level.add(root.val);
            //出队列时将其左右子节点加入队列
            if(root.left!=null){
                queue.offer(root.left);
            }
            if(root.right!=null){
                queue.offer(root.right);
            }
            size--;
        }
        rslt.add(level);
    }
    return rslt;
}

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> list=new ArrayList<List<Integer>>();
    if(root==null) return list;
    Deque<TreeNode> queue=new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        List<Integer> level=new ArrayList<>();
        while(size>0){
            root=queue.poll();
            level.add(root.val);
            if(root.left!=null){
                queue.offer(root.left);
            }
            if(root.right!=null){
                queue.offer(root.right);
            }
            size--;
        }
        list.add(level);
    }
    //反转list
    List<List<Integer>> rslt=new ArrayList<List<Integer>>();
    for(int i=list.size()-1;i>=0;i--){
        rslt.add(list.get(i));
    }
    return rslt;
}

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> rslt=new LinkedList<>();
    if(root==null) return rslt;
    Deque<TreeNode> queue=new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        List<Integer> level=new ArrayList<>();
        while(size>0){
            root=queue.poll();
            level.add(root.val);
            if(root.left!=null){
                queue.offer(root.left);
            }
            if(root.right!=null){
                queue.offer(root.right);
            }
            size--;
        }
        //★将每一层节点加到列表头部
        rslt.add(0,level);
    }
    return rslt;
}

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> rslt=new ArrayList<>();
    if(root==null) return rslt;
    Deque<TreeNode> queue=new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        while(size>0){
            root=queue.poll();
            if(root.left!=null){
                queue.offer(root.left);
            }
            if(root.right!=null){
                queue.offer(root.right);
            }
            //记录每一层的最后一个节点
            if(size==1){
                rslt.add(root.val);
            }
            size--;
        }
    }
    return rslt;
}

class Solution {
    List<Integer> rslt=new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);
        return rslt;
    }
    public void dfs(TreeNode root,int depth){
        if(root==null) return;
        //中右左
        //不是每一个节点都要放进结果集，只把每一层访问的第一个节点放进去。
        //★当前节点深度等于rslt长度时，说明当前节点是本层第一个访问的节点，放入结果集
        if(depth==rslt.size()){
            rslt.add(root.val);
        }
        //访问孩子时记得深度要+1了！
        depth++;
        dfs(root.right,depth);
        dfs(root.left,depth);
    }
}

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> rslt=new ArrayList<Double>();
    Deque<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        double sum=0.0;
        for (int i = 1; i <= size; i++) {
            root = queue.poll();
            sum += root.val;
            if (root.left != null) {
                queue.offer(root.left);
            }
            if (root.right != null) {
                queue.offer(root.right);
            }
        }
        //注意上面的for循环不能直接用size做循环变量，因为结束循环后size=0，0不能做除数。
        //0做除数会报错：Infinite&nbs***bsp;NaN
        rslt.add(sum/size);
    }
    return rslt;
}

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> rslt=new ArrayList<List<Integer>>();
    if(root==null) return rslt;
    Deque<Node> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        List<Integer> level=new ArrayList<Integer>();
        while(size>0){
            root=queue.poll();
            level.add(root.val);
            for(int i=0;i<root.children.size();i++){
                queue.offer(root.children.get(i));
            }
            size--;
        }
        rslt.add(level);
    }
    return rslt;
}

public List<Integer> largestValues(TreeNode root) {
    List<Integer> rslt=new ArrayList<>();
    if(root==null) return rslt;
    Deque<TreeNode> queue=new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        //★-2^31 <= Node.val <= 2^31 - 1
        int max=Integer.MIN_VALUE;
        while(size>0){
            root=queue.poll();
            //更新最大值
            if (root.val > max) {
                max = root.val;
            }
            if(root.left!=null){
                queue.offer(root.left);
            }
            if(root.right!=null){
                queue.offer(root.right);
            }
            size--;
        }
        rslt.add(max);
    }
    return rslt;
}

public Node connect(Node root) {
    if(root==null) return root;
    Deque<Node> que=new ArrayDeque<>();
    que.offer(root);
    while(!que.isEmpty()){
        int size=que.size();
        for(int i=0;i<size;i++){
            Node node=que.poll(); 
            //每层最后一个节点指向null(其实每个node不做任何处理next都是null)
            //node的两个孩子节点：左→右
            if(node.left!=null){
                que.offer(node.left);
                que.offer(node.right);
                node.left.next=node.right;
            }
            //★node的右孩子 和 node兄弟的左孩子 如何处理？
            //如果node不是当前层最后一个节点也不是叶子节点的话，node的右孩子需要指向node兄弟(即node.next)的左孩子，因为兄弟之间都有next连接了，所以可以直接处理
            if(node.next!=null  && node.right!=null){
                node.right.next=node.next.left;
            }
        }
    }
    return root;
}

//★递归逻辑:处理当前节点root
public Node connect(Node root) {
    //终止条件:当前节点root为空或root为叶节点
    if(root==null||root.left==null){
        return root;
    }
    //root不空不为叶节点
    //root的左→右
    root.left.next=root.right;
    //如果root有兄弟，root的右→兄弟的左
    if(root.next!=null){
        root.right.next=root.next.left;
    }
    //层序遍历，从左到右
    connect(root.left);
    connect(root.right);
    //★记得返回！
    return root;
}

public Node connect(Node root) {
    Queue<Node> queue=new LinkedList<>();
    if(root==null) return root;
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        Node preNode=null;
        Node node=null;
        //单层遍历时让上一个节点指向当前节点
        for(int i=0;i<size;i++){
            //如果是每层的第一个节点，他没有上一个节点，但是是别人的上一个节点
            if(i==0){
                preNode=queue.poll();
                //★为了让左右孩子入队，因为下面判断时都是node.left/right
                node=preNode;
            }else{
                //如果不是第一个节点
                node=queue.poll();
                //上一个节点指向当前节点
                preNode.next=node;
                //★更新上一个节点
                preNode=node;
            }
            //左右孩子入队
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }
    return root;
}

public Node connect(Node root) {
    Queue<Node> queue=new LinkedList<>();
    if(root==null) return root;
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        Node preNode=null;
        Node node=null;
        //单层遍历时让上一个节点指向当前节点
        for(int i=0;i<size;i++){
            //如果是每层的第一个节点，他没有上一个节点，但是是别人的上一个节点
            if(i==0){
                preNode=queue.poll();
                //★为了让左右孩子入队，因为下面判断时都是node.left/right
                node=preNode;
            }else{
                //如果不是第一个节点
                node=queue.poll();
                //上一个节点指向当前节点
                preNode.next=node;
                //★更新上一个节点
                preNode=node;
            }
            //左右孩子入队
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
    }
    return root;
}

public int maxDepth(TreeNode root) {
    Queue<TreeNode> queue=new LinkedList<>();
    if(root==null) return 0;
    queue.offer(root);
    int depth=0;
    while(!queue.isEmpty()){
        int size=queue.size();
        for(int i=0;i<size;i++){
            root=queue.poll();
            if(root.left!=null) queue.offer(root.left);
            if(root.right!=null) queue.offer(root.right);
        }
        depth++;
    }
    return depth;
}

public int maxDepth(TreeNode root) {
    if(root==null) return 0;
    //★★这里不用判断左右节点是否存在，因为有上面的终止条件
    //获取左右子树的最大深度
    int leftDepth=maxDepth(root.left);
    int rightDepth=maxDepth(root.right);
    //★二叉树的最大深度 = Max(左子树最大深度,右子树最大深度) + 1(加1是因为算上当前中间节点)
    return Math.max(leftDepth,rightDepth)+1;
}

public int minDepth(TreeNode root) {
    Queue<TreeNode> queue=new LinkedList<>();
    if(root==null) return 0;
    queue.offer(root);
    int depth=0;
    while(!queue.isEmpty()){
        //★注意depth++的位置，只要开始遍历当前层，就把depth++。最大深度是遍历完才++。
        depth++;
        int size=queue.size();
        for(int i=0;i<size;i++){
            root=queue.poll();
            if(root.left==null&&root.right==null) return depth;
            if(root.left!=null) queue.offer(root.left);
            if(root.right!=null) queue.offer(root.right);
        }
    }
    return depth;
}

public int minDepth(TreeNode root) {
    //遇到空节点返回0，表示当前节点的高度为0。
    if(root==null) return 0;
    //获取左子树最小深度
    int leftDepth=minDepth(root.left);
    //获取右子树最小深度
    int rightDepth=minDepth(root.right);
    //★左子树为空右子树不为空，返回右子树最小高度+1
    if(root.left==null&&root.right!=null){
        return rightDepth+1;
    }
    //★同理，右子树为空左子树不为空，返回左子树最小高度+1
    if(root.right==null&&root.left!=null){
        return leftDepth+1;
    }
    //左右子树都不为空，返回二者的最小高度+1
    return Math.min(leftDepth,rightDepth)+1;
}

class Solution {
    //返回值类型和形参
    public TreeNode invertTree(TreeNode root) {
        //终止条件：空节点返回
        if(root==null) return root;
        //递归逻辑(前序)
        //中：交换root(当前节点)的左右子节点
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        //左
        invertTree(root.left);
        //右
        invertTree(root.right);
        return root;
    }
}

    public TreeNode invertTree(TreeNode root) {
        //终止条件：空节点返回
        if(root==null) return root;
        //递归逻辑
        //左
        invertTree(root.left);
        //中：交换root(当前节点)的左右子节点
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        //★右（之前的右成了现在的左）
        invertTree(root.left);
        return root;
    }

public TreeNode invertTree(TreeNode root) {
    if(root==null) return root;
    Queue<TreeNode> queue=new LinkedList<>(); 
    queue.offer(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        for(;size>0;size--){
            TreeNode node=queue.poll();
            //交换左右子节点
            TreeNode temp=node.left;
            node.left=node.right;
            node.right=temp;
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
    }
    return root;
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
                //判断根节点的左右子树是否对称
        return compare(root.left,root.right);
    }
    //返回值类型:左右子树是否可翻转; 形参:当前节点的左右子树
    public boolean compare(TreeNode left,TreeNode right){
        //终止条件:
        //1. 左为空右不为空，不对称
        //2. 左不为空右为空，不对称
        //3. 左右都为空，对称但不同继续向下遍历了
        //4. 左右都不为空但值不相等，不对称
        if(left==null&&right!=null) return false;
        if(left!=null&&right==null) return false;
        if(left==null&&right==null) return true;
        if(left!=null&&right!=null&&left.val!=right.val) return false;
        //左右不为空且值相等，可能对称且要继续向下遍历
        //递归逻辑:判断左右子树是否对称(是否可以翻转)
        //如何判断两棵子树可以翻转?——同一层对称置的两个节点的外侧节点与外侧节点相同，内侧节点与内侧节点相同，则可以翻转
        //比较外侧节点与外侧节点
        boolean outNode=compare(left.left,right.right);
        //比较内侧节点与内侧节点
        boolean inNode=compare(left.right,right.left);
        //内外侧都相同(&&)才可以翻转
        return outNode && inNode;
    }
}

class Solution {
    //表示统计以root为根节点的树的节点个数。
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        int countLeft=countNodes(root.left);
        int countRight=countNodes(root.right);
        //+1是当前节点，比如说传进来的root是叶子节点，表示计算以root为根的树的节点个数(1个)。上面的countLeft和countRight都是0，返回以root为根的树的节点个数=0+0+1。
        return countLeft+countRight+1;
    }
}

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        Deque<TreeNode> que=new ArrayDeque<>();
        que.offer(root);
        int count = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.peek();
                que.poll();
                count++;   // 记录节点数量
                if (node.left!=null) que.offer(node.left);
                if (node.right!=null) que.offer(node.right);
            }
        }
        return count;
    }
}

最左侧深度等于最右侧深度，则该子树是满二叉树(如下面第一第二幅图)。因为前提是完全二叉树，所以不会出现下图三虽然左右深度相同但不是满二叉树的情况。
                
【具体实现】判断其子树是不是满二叉树，如果是则利用公式计算这个满二叉子树的节点个数；如果不是，继续递归。★★要注意终止条件有两个！空节点返回和满二叉子树返回！

class Solution {
    //1. 返回值类型和形参
    public int countNodes(TreeNode root) {
        //2. 终止条件
        //2.1 空节点返回0
        if(root==null) return 0;
        //2.2 子树是满二叉树，返回子树节点个数
        //左侧深度;右侧深度(我们规定根节点深度为0)
        int leftDepth=0;
        int rightDepth=0;
        TreeNode leftNode=root.left;
        TreeNode rightNode=root.right;
        //一直往左深度遍历，得到左侧深度
        while(leftNode!=null){
            leftNode=leftNode.left;
            leftDepth++;
        }
        //一直往右深度遍历，得到右侧深度
        while(rightNode!=null){
            rightNode=rightNode.right;
            rightDepth++;
        }
        //左侧深度等于右侧深度，说明是满二叉树，直接根据公式返回满二叉树的节点个数
        if(leftDepth==rightDepth) return (2<<leftDepth)-1;//★相当于2^(leftDepth+1)-1
        //3. 单层递归逻辑
        int countLeft=countNodes(root.left);
        int countRight=countNodes(root.right);
        return countLeft+countRight+1;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        //计算树的高度，根据高度判断是否平衡
        return getTreeHigh(root)!=-1;
    }
    //用来计算树的高度并判断是不是平衡二叉树，用-1来表示非平衡二叉树
    public int getTreeHigh(TreeNode root){
        //终止条件
        if(root==null) return 0;
        int leftHigh=getTreeHigh(root.left);
        //★如果当前树的左子树高度为-1，说明左子树不是平衡二叉树，那么当前树也不是平衡二叉树，当前树就返回-1表示自己不是平衡二叉树
        if(leftHigh==-1) return -1;
        int rightHigh=getTreeHigh(root.right);
        //同上
        if(rightHigh==-1) return -1;
        //左右子树都是平衡二叉树，看二者高度差
        if(Math.abs(leftHigh-rightHigh)<=1){
            //左右子树高度差绝对值不超过1，当前树是平衡二叉树，返回当前树的高度
            return Math.max(leftHigh,rightHigh)+1;
        }else{
            ★//左右子树高度差绝对值超过1了，当前树不是平衡二叉树，返回-1
            return -1;
        }
    }
}

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> rslt=new ArrayList<>();
        //用来记录单条路径
        List<Integer> path=new ArrayList<>();
        getPath(root,rslt,path);
        return rslt;
    }
    //前序递归遍历获取每一条路径，并加入结果集
    public void getPath(TreeNode root,List<String> rslt,List<Integer> path) {
        //中——把当前节点加入path中(★因为终止条件比较特殊，是叶子节点，而叶子节点也需要加到path中，所以这一步要在终止条件之前)
        path.add(root.val);
        //★终止条件:遇到叶子节点就停止递归(因为空节点不需要加到路径中)
        if(root.left==null&&root.right==null){
            //root为叶子节点说明当前路径到头了，此时需要将path中保存的当前路径的节点按要求拼成字符串存到结果集中
            StringBuilder sb=new StringBuilder();
            //路径终点不需要->,需要单独处理,因此这里只遍历到倒数第二个元素即可
            for(int i=0;i<path.size()-1;i++){
                sb.append(String.valueOf(path.get(i))+"->");
            }
            //路径终点单独处理
            sb.append(String.valueOf(path.get(path.size()-1)));
            //一条路径完毕，加到结果集中
            rslt.add(sb.toString());
            return;
        }
        //递归逻辑——前序遍历
        //中(在最前面，整体上还是中左右的逻辑顺序)
        //左
        if(root.left!=null){
            getPath(root.left,rslt,path);
            //★path只是单条路径，不能一直往里面加节点，因此还需要从里面删节点。这里就要用到回溯。
            //★回溯和递归是一一对应的，有一个递归，就要有一个回溯。
            path.remove(path.size()-1);
        }
        //右
        if(root.right!=null){
            getPath(root.right,rslt,path);
            //★回退(回溯)
            path.remove(path.size()-1);
        }
    }
}

class Solution {
    //求以root为根的二叉树的左叶子之和
    public int sumOfLeftLeaves(TreeNode root) {
        //终止条件
        if(root==null) return 0;
        //递归逻辑
        //如果当前节点有左节点且左节点为叶子节点的话，记录该左叶子的值
        int rslt=0;
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            rslt=root.left.val;
            //★左节点为叶子节点，不需要递归左边了，再知道右子树的左叶子之和即可
            return sumOfLeftLeaves(root.right)+rslt;
        }
        //左节点不是叶子节点
        //以root为根的二叉树的左叶子之和=左子树左叶子之和+右子树左叶子之和
        return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        //层序遍历，返回最后一层最左边的值
                //记录当前层第一个节点的值，层序遍历时，更新rslt，层序遍历结束时，rslt记录的就是最后一层最左边的值，即左下角的值。
        int rslt=0;
        //题目规定至少有一个节点
        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                root=queue.poll();
                //获取当前层第一个节点的值
                if(i==0) rslt=root.val;
                if(root.left!=null) queue.offer(root.left);
                if(root.right!=null) queue.offer(root.right);
            }
        }
        return rslt;
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            //从右往左
            if (root.right != null) queue.offer(root.right);
            if (root.left != null) queue.offer(root.left);
        }
        return root.val;
    }
}

class Solution {
    List<Integer> path=new ArrayList<>();
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        path.add(root.val);
        if(root.left==null&&root.right==null){
            int sum=0;
                        //记录该路径节点之和             for(int i=0;i<path.size();i++){
                sum+=path.get(i);
            }
            if(sum==targetSum) return true;
        }
                //★不能放下面的if里面，那就成if的局部变量了。而且初始化时要置为false，因为
        boolean leftPath=false;
        boolean rightPath=false;
        if(root.left!=null){
            leftPath=hasPathSum(root.left,targetSum);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            rightPath=hasPathSum(root.right,targetSum);
            path.remove(path.size()-1);
        }
                //
        return leftPath||rightPath;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //终止条件
        if(root==null) return false;
        targetSum=targetSum-root.val;
        //叶子节点表示到路径终点了，同时如果targetSum减到0了说明路径之和满足目标值了，返回true
        if(root.left==null&&root.right==null){
            if(targetSum==0) return true;
        }
        //递归逻辑
        if(root.left!=null){
            boolean leftPath=hasPathSum(root.left,targetSum);
            //如果递归函数返回true，说明找到了合适的路径，应该立刻返回true。(包含了回溯的思想，这里的targetSum回到了当前的值)
            if(leftPath) return true;
        }
        if(root.right!=null){
            boolean rightPath=hasPathSum(root.right,targetSum);
            if(rightPath) return true;
        }
        //如果往左和往右都没找到合适路径，就返回false
        return false;
    }
}

class Solution {
        List<List<Integer>> rslt=new ArrayList<List<Integer>>();
        List<Integer> path=new ArrayList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root==null) return rslt;
        getPath(root,targetSum);
        return rslt;
    }
    public void getPath(TreeNode root,int targetSum){
                //★对中的操作一定要放在if判断的前面，不然叶子节点就加不到path里了！
        path.add(root.val);
        targetSum-=root.val;
        if(root.left==null&&root.right==null){
            if(targetSum==0){
                rslt.add(new ArrayList(path));
            }
            return;
        }
                //★不能保证左右节点一定存在，所以要先进行非空判断！
        if(root.left!=null){
            getPath(root.left,targetSum);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            getPath(root.right,targetSum);
            path.remove(path.size()-1);
        }
        return;
    }
}

• 第一步：如果任一数组大小为零，说明是空节点(null)了。
• 第二步：如果不为空，那么后序数组最后一个元素作为节点元素（根节点）。
• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点。
• 第四步：根据切割点切割中序数组，切成中序左数组和中序右数组。
• 第五步：根据中序左数组长度切割后序数组，切成后序左数组和后序右数组。(因为中序左数组长度=后序左数组长度)
• 第六步：递归处理左区间和右区间，获取左右子节点
  ★在递归的过程中要始终保持区间一致！

class Solution {
    //★用来保存中序数组inorder中各元素及对应的下标，不用每次都用循环去找root在中序数组中的下标
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map=new HashMap<>();
        //保存中序数组inorder中各元素及对应的下标
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    //根据中序和后序数组，找出根节点及其左右子节点。
    //切割数组采用start和end指针来标记，而不是真正把数组切割:通过inorder,inStart,inEnd确定切割后的数组。
    public TreeNode findNode(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd) {
        //终止条件:如果任一数组里没有元素了，说明是空节点
        if(inStart>=inEnd||postStart>=postEnd) return null;
        //递归逻辑
        //1.根据后序数组的最后一个元素构建根节点
        int rootVal=postorder[postEnd-1];
        TreeNode root=new TreeNode(rootVal);
        //2.根据后序切割中序——找的中序数组中根节点的位置，以此为基准切割中序数组
        int rootIdx=map.get(rootVal);
        //3.根据中序切割后序——记录中序数组切割后的左子树节点的长度，用来切割后序数组
        int leftLength=rootIdx-inStart;
        //4.构建左子节点
        root.left=findNode(inorder,inStart,rootIdx,postorder,postStart,postStart+leftLength);
        //5.构建右子节点
        root.right=findNode(inorder,rootIdx+1,inEnd,postorder,postStart+leftLength,postEnd-1);
        //记得返回根节点！！！
        return root;
    }
}

class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        //左闭右开
        return findNode(preorder,0,preorder.length,inorder,0,inorder.length);
    }
    public TreeNode findNode(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd) {
        if(preStart>=preEnd||inStart>=inEnd) return null;
        int rootVal=preorder[preStart];
        TreeNode root=new TreeNode(rootVal);
        int rootIdx=map.get(rootVal);
        int leftLen=rootIdx-inStart;
        root.left=findNode(preorder,preStart+1,preStart+leftLen+1,inorder,inStart,rootIdx);
        root.right=findNode(preorder,preStart+leftLen+1,preEnd,inorder,rootIdx+1,inEnd);
        return root;
    }
}

class Solution {
    //左闭右开
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return findNode(nums,0,nums.length);
    }
    public TreeNode findNode(int[] nums,int start,int end){
        //数组为空，空节点
        if(start>=end) return null;
        //找到当前数组的最大值
        int maxIdx=findMaxIdx(nums,start,end);
        TreeNode root=new TreeNode(nums[maxIdx]);
        //递归处理左部分和右部分
        root.left=findNode(nums,start,maxIdx);
        root.right=findNode(nums,maxIdx+1,end);
        return root;
    }
    public int findMaxIdx(int[] nums,int start,int end){
        int maxIdx=-1;
        int max=-1;
        for(int i=start;i<end;i++){
            if(max<nums[i]){
                max=nums[i];
                maxIdx=i;
            }
        }
        return maxIdx;
    }
}

class Solution {
    //形参和返回值类型：要合并两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //终止条件
        if(root1==null&&root2==null) return null;
        if(root1==null) return root2;
        if(root2==null) return root1;
        //递归逻辑——前序同时遍历两个二叉树
        TreeNode root=new TreeNode(root1.val+root2.val);
        root.left=mergeTrees(root1.left,root2.left);
        root.right=mergeTrees(root1.right,root2.right);
        return root;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null) return root;
        while(root!=null){
            if(root.val>val){
                root=root.left;
            }else if(root.val<val){
                root=root.right;
            }else{
                return root;
            }
        }
        //val不在树中
        return null;
    }
}

class Solution {
    //前序递归遍历
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null) return null;
        if(root.val==val) return root;
        TreeNode rslt=null;
        if(root.val>val) rslt=searchBST(root.left,val);
        if(root.val<val) rslt=searchBST(root.right,val);
        return rslt;
    }
}

class Solution {
    List<Integer> list=new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        //获取中序遍历序列
        inOrder(root);
        //判断中序遍历序列是否严格单调递增
        for(int i=0;i<list.size();i++){
            if(i>0&&list.get(i)<=list.get(i-1)){
                return false;
            }
        }
        return true;
    }
    //获取中序遍历序列
    public void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }
}

class Solution {
    //★用来记录上一个节点
    TreeNode pre=null;
    //中序遍历并判断是否严格递增
    public boolean isValidBST(TreeNode root) {
        //终止条件:二叉搜索树可以为空!
        if (root == null) return true;
        // 左
        boolean left = isValidBST(root.left);
        // ★中
        if (pre != null && root.val <= pre.val) {//不满足严格递增。★要注意判断pre不为空，因为可能是序列中的第一个节点，他没有上一个节点。
            return false;
        }
        pre = root;//记录上一个节点。★因为是中序遍历左中右，所以中序序列中，“右”的上一个节点是“中”，所以“中”之后要更新pre！
        // 右
        boolean right = isValidBST(root.right);
        return left&&right;
    }
}

class Solution {
    List<Integer> list=new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        int min=Integer.MAX_VALUE;
        for(int i=1;i<list.size();i++){
            min=Math.min(min,Math.abs(list.get(i)-list.get(i-1)));
        }
        return min;
    }
    public void inorder(TreeNode root){
        if(root==null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}

class Solution {
    int min=Integer.MAX_VALUE;
    //用来记录上一个节点
    TreeNode pre=null;
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return min;
    }
    //中序遍历，每次比较【当前节点与前一节点差值】与最小值min的大小，将较小的保存在min中。
    public void inorder(TreeNode root){
        if(root==null) return;
        inorder(root.left);
        if(pre!=null){
            //★因为中序得到的已经是递增的了，所以root.val一定比pre.val大，所以不需要abs了
                        //min=Math.min(min,Math.abs(pre.val-root.val));
            min=Math.min(min,root.val-pre.val);
        }
        //记录上一个节点
        pre=root;
        inorder(root.right);
    }
}

class Solution {
    List<Integer> list=new ArrayList<>();
    //用来记录当前统计的值的频率
    int count=0;
    //用来记录最大频率
    int maxCount=0;
    TreeNode pre=null;
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] rslt=new int[list.size()];
        //list->int[] rslt
        for(int i=0;i<list.size();i++){
            rslt[i]=list.get(i);
        }
        return rslt;
    }
    public void inorder(TreeNode root){
        //终止条件
        if(root==null) return;
        //左
        inorder(root.left);
        //中★
        if(pre==null){//★第一个节点
            count=1;
        }else if(root.val==pre.val){//当前节点值=上一个节点值
            count++;
        }else{//★当前节点值不等于上一个节点值，重新统计当前节点的出现频率
            count=1;//为什么不是0呢？因为现在已经统计到了当前节点，已经出现一次了，所以是1不是0
        }
        //如果统计的频率count比最高频率maxCount大
        if(count>maxCount){
            //★清空结果集，因为结果集之前的元素都失效了。
            list.clear();
            //将新值加到结果集中
            list.add(root.val);
            //更新最高频率
            maxCount=count;
        }else if(count==maxCount){//如果统计的频率count与最高频率maxCount相等，说明树中有不止一个众数
            //将新众数加到结果集中
            list.add(root.val);
        }
        pre=root;
        //右
        inorder(root.right);
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //pq比当前节点都小，说明pq一定在当前节点的左子树，因此往左遍历
        if(root.val>p.val&&root.val>q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        //pq比当前节点都大，生命pq一定在当前节点的右子树，因此往右遍历
        if(root.val<p.val&&root.val<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        //else: (root.val>p.val&&root.val<q.val)||(root.val>q.val&&root.val<p.val)
        //即当前节点在pq之间，一定是最近公共祖先
        return root;
    }
}

class Solution {
    //递归建树
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //如果遇到空节点了，说明找到了插入位置，直接返回新节点
        if(root==null) return new TreeNode(val);
        //递归创建右子树
        if(val>root.val){
            root.right=insertIntoBST(root.right,val);
        }
        //递归创建左子树
        if(val<root.val){
            root.left=insertIntoBST(root.left,val);
        }
        return root;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //终止条件
        if(root==null) return null;
        //1.如果root不在区间内，又分两种情况：
        //1.1 root比low还小，说明root左子树一定都小于low，所以只处理右子树即可
        if(root.val<low){
            return trimBST(root.right,low,high);
        }
        //1.2 root比high还大，说明root右子树一定都大于high，所以只处理左子树即可
        if(root.val>high){
            return trimBST(root.left,low,high);
        }
        //2.如果root在区间[low,high]中，处理左右子树
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);

        return root;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        //左闭右闭
        int left=0;
        int right=nums.length-1;
        return buildBST(nums,left,right);
    }
    public TreeNode buildBST(int[] nums,int left,int right){
        //终止条件：★数组里没元素了，返回空节点
        if(left>right) return null;
        //递归逻辑：中间元素作为根节点，递归建树
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=buildBST(nums,left,mid-1);
        root.right=buildBST(nums,mid+1,right);
        return root;
    }
}

class Solution {
    //★8+0=8
    int num=0;//记录上一个节点的值，对于第一个节点来说，他的上一个节点是null，值是0！
    public TreeNode convertBST(TreeNode root) {
        //终止条件
        if(root==null) return null;
        //递归逻辑
        //右
        root.right=convertBST(root.right);
        //中
        root.val+=num;//将上一个节点的值加到当前节点
        num=root.val;//更新上一个节点的值
        //左
        root.left=convertBST(root.left);
        return root;
    }
}

class Solution {
    //用来记录上一个节点，对于第一个节点来说，他的上一个节点为空，但是值为0。所以这里我们不能写pre=null！
    TreeNode pre=new TreeNode(0);
    public TreeNode convertBST(TreeNode root) {
        //终止条件
        if(root==null) return null;
        //递归逻辑
        //右
        root.right=convertBST(root.right);
        //中
        root.val+=pre.val;
        pre.val=root.val;
        //左
        root.left=convertBST(root.left);
        return root;
    }
}