树

226. 翻转二叉树

思路1：递归： 将当前的root.left指向假设已经翻转完成的右子树，root.right指向已经翻转完成的左子树 时间复杂度：O(n) 二叉树的节点个数是n 空间复杂度：O(n) 最坏情况下二叉树退化为链表 最好情况下满二叉树O(logn)

class Solution {
    public TreeNode invertTree(TreeNode root) {
         if(root==null)//节点为空时直接返回
                return root;
          TreeNode tmp=root.left;//保存左子树
          root.left=invertTree(root.right);//left指向反转完成的右子树
          root.right=invertTree(tmp);//右子树指向反转完成的左子树
          return root;
    }
}

思路2：层次遍历，对每一层的的节点进行交换，层次遍历需要使用到队列 时间复杂度: O(n) 空间复杂度：O(logn) 最坏情况下二叉树是满二叉树，最后一层节点个数是logn

class Solution {
    public TreeNode invertTree(TreeNode root) {
       if(root==null)
         return root;
       Queue<TreeNode> q=new LinkedList<>();
       q.offer(root);
       while(!q.isEmpty())
       {
           TreeNode node=q.poll();
           if(node.left!=null)
                q.offer(node.left);
           if(node.right!=null)
                q.offer(node.right);
            TreeNode tmp=node.left;
            node.left=node.right;
            node.right=tmp;
       }
       return root;
    }
}

116. 填充每个节点的下一个右侧节点指针

思路1：递归

class Solution {
    public Node connect(Node root) {
        if(root==null)
            return root;
        //根节点只有一个 可以不用处理 next默认为null
        connect(root.left,root.right);//从第2层开始处理节点
        return root;
    }
    public void connect(Node node1,Node node2)
    {
        if(node1==null||node2==null)//遇到空节点 返回
            return;
        node1.next=node2;//node1连接node2
        connect(node1.left,node1.right);//node1的左子节点连接右子节点
        connect(node2.left,node2.right);//node2的左子节点连接右子节点
        connect(node1.right,node2.left);//node1的右子节点连接node2的左子节点
    }
}
//O(n)
//O(logn)  完全二叉树

思路2： 层次遍历

class Solution {
    public Node connect(Node root) {
      if(root==null)
        return root;
      Queue<Node> q=new LinkedList<>();
      q.offer(root);
      while(!q.isEmpty())
      {
          int sz=q.size();
          for(int i=0;i<sz;i++)
          {
              Node node=q.poll();
              if(node.left!=null)
                 q.offer(node.left);
              if(node.right!=null)
                q.offer(node.right);
              if(i<sz-1)//不考虑最后一个节点的next
                node.next=q.peek();//q.peek()是当前节点同一层的下一个节点
          }
      }
      return root;
    }
}
//O(n)
//O(logn)  完全二叉树

思路3：从根节点开始，由于第 0 层只有一个节点，所以不需要连接，直接为第 11层节点建立 next 指针即可。该算法中需要注意的一点是，当我们为第 N层节点建立 next指针时，处于第 N−1层。当第 N 层节点的 next 指针全部建立完成后，移至第 N层，建立第 N+1层节点的 next指针。 遍历某一层的节点时，这层节点的 next 指针已经建立。因此我们只需要知道这一层的最左节点，就可以按照链表方式遍历，不需要使用队列。

class Solution {
    public Node connect(Node root) {
        if(root==null)
            return root;
        Node leftmost=root;//leftmost表示该层中最左边的节点
        while(leftmost.left!=null)
        {
            Node start=leftmost;//start遍历一层中的节点 初始化为最左边的节点
            while(start!=null)
            {
                start.left.next=start.right;//同一父节点的左右节点连接
                if(start.next!=null)
                    start.right.next=start.next.left;//不同父节点的右左节点连接
                start=start.next;//start指向同层的下一个节点
            }
            leftmost=leftmost.left;//进行下一层的处理
        }
        return root;
    }
}
//O(n)
//O(1)

114. 二叉树展开为链表

思路1：先获得二叉树的先序遍历序列，如何逐个将序列节点连接即可 获得先序序列可以直接采用递归，也可以使用栈迭代获取，二者本质上一样

class Solution {
    ArrayList<TreeNode> list=new ArrayList<>();
    public void flatten(TreeNode root) {
       if(root!=null)
       {
            LinkedList<TreeNode> st=new LinkedList<>();
            st.push(root);
            while(!st.isEmpty())
            {
                TreeNode node=st.pop();
                list.add(node);
                if(node.right!=null)
                    st.push(node.right);
                if(node.left!=null)
                    st.push(node.left);
            }
       }
        for(int i=1;i<list.size();i++)
        {
            TreeNode pre=list.get(i-1),cur=list.get(i);
            pre.left=null;
            pre.right=cur;
        }
    }
}
//O(n)
//O(n)

class Solution {
    ArrayList<TreeNode> list=new ArrayList<>();
    public void flatten(TreeNode root) {
       if(root!=null)
       {
            LinkedList<TreeNode> st=new LinkedList<>();
            st.push(root);
            while(!st.isEmpty())
            {
                TreeNode node=st.pop();
                list.add(node);
                if(node.right!=null)
                    st.push(node.right);
                if(node.left!=null)
                    st.push(node.left);
            }
       }
        for(int i=1;i<list.size();i++)
        {
            TreeNode pre=list.get(i-1),cur=list.get(i);
            pre.left=null;
            pre.right=cur;
        }
    }
}

思路2：原地修改
关键点： 对于当前节点cur, 如果其左子树为空，则cur就是cur.right的前继节点；如果cur的左子树不为空，则左子树中的最下最右的节点是cur.right的前继节点

1. cur的左子树不为空，找到左子树中的最下最右节点pre
2. pre.right=cur.right
3. cur.right=cur.left cur.left=null

class Solution {

    public void flatten(TreeNode root) {
        TreeNode cur=root;
        while(cur!=null)
        {
            if(cur.left!=null)
            {
                TreeNode pre=cur.left;
                while(pre.right!=null)
                    pre=pre.right;//pre在循环结束后指向cur左子树中最下最右的节点
                pre.right=cur.right;
                cur.right=cur.left;
                cur.left=null;

            }
            cur=cur.right;//cur的左子树为空 cur就是cur.right的前继节点 继续往下处理
        }

    }

}
//O(n)
//O(1)

654. 最大二叉树

先找到当前应该创建的根节点，根节点是当前数组中的最大值，可以用一个函数来获取数组当前范围内最大值的下标

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
            return createTree(nums,0,nums.length-1);
    }
    public TreeNode createTree(int[] nums,int left,int right)
    {
        if(left>right)
            return null;
        int index=getMax(nums,left,right);
        TreeNode root=new TreeNode(nums[index]);
        root.left=createTree(nums,left,index-1);
        root.right=createTree(nums,index+1,right);
        return root;
    }
    public int getMax(int[] nums,int left,int right)
    {
        int index=left;
        for(int i=left+1;i<=right;i++)
        {
            if(nums[i]>nums[index])
                index=i;
        }
        return index;
    }


}
//O(n*n)   n次递归 每次递归调用getMax函数
//O(n) 最坏情况下二叉树为链表->栈的深度是n  平均情况下栈的深度是logn

105. 从前序与中序遍历序列构造二叉树

思路1：递归

class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i],i);//map记录中序序列中的元素和其位置的键值对
        return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode buildTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd)
    {
        if(preStart>preEnd)
            return null;
        int rootVal=preorder[preStart];
        TreeNode root=new TreeNode(rootVal);
        int index=map.get(rootVal);//index是preOrder中的根节点在inOrder中出现的位置
        int leftSize=index-inStart;//0 1 2 root 4 5 6 index-1-instart+1=index-instart
        //下一次创建的左子树的根节点是preStart+1 
        root.left=buildTree(preorder,preStart+1,preStart+leftSize,inorder,inStart,index-1);
        //下一次创建的左子树的根节点是preStart+leftSize+1 
        root.right=buildTree(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inEnd);
        return root;

    }
}
//O(n)
//O(n) map空间n  递归深度h h<n

方法2：迭代
假设前序序列中两个相连的节点u v, u v节点有以下两种情况：

1. u有左儿子—>v是u的左子节点
2. u没有左儿子—>v是u的右子节点或u的祖先节点的右子节点

算法流程：

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
       LinkedList<TreeNode> st=new LinkedList<>();
       int index=0;
       TreeNode root=new TreeNode(preorder[0]);
       st.push(root);
       for(int i=1;i<preorder.length;i++)
       {
           int preorderVal=preorder[i];
           TreeNode node=st.peek();
           if(node.val!=inorder[index])
           {
               node.left=new TreeNode(preorderVal);
               st.push(node.left);
           }
           else
           {
               while(!st.isEmpty()&&st.peek().val==inorder[index])
               {
                   index++;
                   node=st.pop();
               }
               node.right=new TreeNode(preorderVal);
               st.push(node.right);
           }
       }
       return root;
    }

}
//O(n)
//O(n)

106. 从中序与后序遍历序列构造二叉树

思路1：递归

class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;i++)
            map.put(inorder[i],i);//map记录中序序列中的元素和其位置的键值对
        return buildTree(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode buildTree(int[] postorder,int postStart,int postEnd,int[] inorder,int inStart,int inEnd)
    {
        if(postStart>postEnd)
            return null;
        int rootVal=postorder[postEnd];
        TreeNode root=new TreeNode(rootVal);
        int index=map.get(rootVal);
        int leftSize=index-inStart;
        root.left=buildTree(postorder,postStart,postStart+leftSize-1,inorder,inStart,index-1);
        root.right=buildTree(postorder,postStart+leftSize,postEnd-1,inorder,index+1,inEnd);
        return root;
    }
}
//O(n)
//O(n)

思路2： 和105题思路类似，但是过程相反 假设后序序列中两个相连的节点u v, u v节点有以下两种情况：

1. v有右儿子—>u是v的右子节点
2. v没有右儿子—>u是v的左子节点或v的祖先节点的左子节点

class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
       LinkedList<TreeNode> st=new LinkedList<>();
       int index=inorder.length-1;
       TreeNode root=new TreeNode(postorder[postorder.length-1]);
       st.push(root);
       for(int i=postorder.length-2;i>=0;i--)
       {
           int postorderVal=postorder[i];
           TreeNode node=st.peek();
            if(node.val!=inorder[index])
           {
               node.right=new TreeNode(postorderVal);
               st.push(node.right);
           }
           else
           {
               while(!st.isEmpty()&&st.peek().val==inorder[index])
               {
                   index--;
                   node=st.pop();
               }
               node.left=new TreeNode(postorderVal);
               st.push(node.left);
           }
       }
       return root;
    }

}
//O(n)
//O(n)

257. 二叉树的所有路径

思路1：递归，使用一个实例变量StringBuilder sb来记录dfs过程中的路径，在返回上一层时使用sb.delete()方法删除当前层加入的字符串，当遇到叶子节点时，将路径加入到答案集合中

class Solution {
     List<String> ans=new ArrayList<>();
     StringBuilder sb=new StringBuilder();
    public List<String> binaryTreePaths(TreeNode root) {
       dfs(root);
       return ans;

    }
    public void dfs(TreeNode root)
    {
        if(root==null)
            return;
        int sz=sb.length();//未加入新的节点的sb长度
        sb.append(root.val);
        if(root.left==null&&root.right==null)
        {

            ans.add(sb.toString());
            sb.delete(sz,sb.length());//sz-sb.length的部分是新加入的 由于要返回上一级 需要删除
            return;
        }
        sb.append("->");
        dfs(root.left);
        dfs(root.right);
        sb.delete(sz,sb.length());
    }
}
//时间复杂度  二叉树退化为链表时 O(n)  完全二叉树时 nlogn  叶子节点n/2个  路径长logn
//空间复杂度 sb中最多存储n个节点字符  O(n)

思路2：迭代 使用队列进行层次遍历，但是需要使用两个队列，一个用来保存节点，一个用来保存当前节点对应的路径

class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans=new ArrayList<>();
        LinkedList<TreeNode> nodeQ=new LinkedList<>();
        LinkedList<String> pathQ=new LinkedList<>();
        nodeQ.offer(root);
        pathQ.offer(root.val+"");
        while(!nodeQ.isEmpty())
        {
            TreeNode node=nodeQ.poll();
            String path=pathQ.poll();
            if(node.left!=null)
            {
                 //System.out.println(node.left.val);
                nodeQ.offer(node.left);
                pathQ.offer(new StringBuilder(path).append("->").append(node.left.val).toString());
            }
            if(node.right!=null)
            {
                 //System.out.println(node.right.val);
                nodeQ.offer(node.right);
                pathQ.offer(new StringBuilder(path).append("->").append(node.right.val).toString());
            }
            if(node.left==null&&node.right==null)
            {
               // System.out.println(path);
                ans.add(path);
            }
        }
       return ans;

    }



}
//时间复杂度 O(n^2)
//空间复杂度 O(n^2)

652. 寻找重复的子树

思路1：将以node为根节点的子树用一个字符串来表示，同时使用map记录该字符串出现的次数，如果次数出现超过2次说明重复，将其加入答案

class Solution {
    List<TreeNode> ans=new ArrayList<>();
    HashMap<String,Integer> map=new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) { 
        dfs(root);
        return ans;
    }
    public String dfs(TreeNode node)
    {
       if(node==null)
        return "#";
       String left=dfs(node.left);
       String right=dfs(node.right);
       String subTree=left+","+right+","+node.val;
       map.put(subTree,map.getOrDefault(subTree,0)+1);
       if(map.get(subTree)==2)
            ans.add(node);
        return subTree;
    }

}
//O(n^2)
//O(n^2)

上面的代码每次都要拼接字符串，dfs的返回值是字符串，可以用一个整型id来表示一个子树，相同的子树id相同，这样就可以使得dfs返回的值是一个整数

class Solution {
    List<TreeNode> ans=new ArrayList<>();
    HashMap<String,Integer> map1=new HashMap<>();//map1记录子树和id的映射
    HashMap<Integer,Integer> map2=new HashMap<>();//map2记录子树id和id出现次数的映射
    int t=1;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) { 
        dfs(root);
        return ans;
    }
    public int dfs(TreeNode node)
    {
       if(node==null)
            return 0;//空节点用0表示
       int left=dfs(node.left);
       int right=dfs(node.right);
       String subTree=left+","+right+","+node.val;
       int id;
       if(map1.containsKey(subTree))//当前的子树已经出现过 使用之前的id
            id=map1.get(subTree);
        else//当前的子树没有出现过
        {
            id=t++;//使用新的id
            map1.put(subTree,id);//map1中添加新的映射
        }
        map2.put(id,map2.getOrDefault(id,0)+1);//map2中将对应的子树id次数加一
        if(map2.get(id)==2)//如果重复则添加
            ans.add(node);
        return id;
    }

}
//O(n)
//O(n)

297. 二叉树的序列化与反序列化

思路1：前序遍历，使用StringBuilder连接前序遍历的节点序列，然后将StringBuilder转化成String，到此为止，二叉树的序列化完成；然后将传递给反序列化的参数String进行分割，得到一个字符串数组，将字符串数组的内容放进LinkedList中，方便后面进行处理

public class Codec {
    String NULL="#";//空节点表示符号
    String SEP=",";//分割符号
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        serialize(root,sb);
        return sb.toString();

    }
    public void serialize(TreeNode root,StringBuilder sb)
    {
        if(root==null)
        {
            sb.append(NULL).append(SEP);//遇到空节点
            return;
        }
        sb.append(Integer.toString(root.val)).append(SEP);//加入根节点
        //拓展左右子树
        serialize(root.left,sb);
        serialize(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        String [] s=data.split(SEP);//用分隔符获得一个节点数组
        LinkedList<String> nodes=new LinkedList<>();
        for(int i=0;i<s.length;i++)
        {
            nodes.add(s[i]);//使用list存储 方便后面操作
        }
        return deserialize(nodes);

    }
    public TreeNode deserialize(LinkedList<String> nodes)
    {
        String firstNode=nodes.poll();
        if(firstNode.equals(NULL))//当前的是空节点 返回null
            return null;
        TreeNode root=new TreeNode(Integer.parseInt(firstNode));//创建根节点
        root.left=deserialize(nodes);//反序列化左子树
        root.right=deserialize(nodes);//反序列化右子树
        return root;

    }
}
//O(n)
//O(n)

思路2：后序遍历，步骤和前序遍历相同，需要改动几个地方

public class Codec {
    String NULL="#";//空节点表示符号
    String SEP=",";//分割符号
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        serialize(root,sb);
        return sb.toString();

    }
    public void serialize(TreeNode root,StringBuilder sb)
    {
        if(root==null)
        {
            sb.append(NULL).append(SEP);//遇到空节点
            return;
        }

        //拓展左右子树
        serialize(root.left,sb);
        serialize(root.right,sb);
        sb.append(Integer.toString(root.val)).append(SEP);//加入根节点  改动1
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        String [] s=data.split(SEP);//用分隔符获得一个节点数组
        LinkedList<String> nodes=new LinkedList<>();
        for(int i=0;i<s.length;i++)
        {
            nodes.add(s[i]);//使用list存储 方便后面操作
        }
        return deserialize(nodes);

    }
    public TreeNode deserialize(LinkedList<String> nodes)
    {
        String firstNode=nodes.removeLast();//改动2
        if(firstNode.equals(NULL))//当前的是空节点 返回null
            return null;
        TreeNode root=new TreeNode(Integer.parseInt(firstNode));//创建根节点
        root.right=deserialize(nodes);//反序列化左子树  改动3
        root.left=deserialize(nodes);//反序列化右子树     改动4
        return root;

    }
}
//O(n)
//O(n)

思路3：层次遍历

public class Codec {
    String NULL="#";//空节点表示符号
    String SEP=",";//分割符号
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)//root为null返回空串
            return "";
        StringBuilder sb=new StringBuilder();
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty())
        {
            TreeNode node=q.poll();
            if(node==null)//空节点加入NULL标志
            {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(node.val).append(SEP);
            q.offer(node.left);//这里不管left是不是null都要加入队列 因为null也需要处理
            q.offer(node.right);


        }
        return sb.toString();

    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0)
            return null;
        String [] nodes=data.split(SEP);//用分隔符获得一个节点数组
        TreeNode root=new TreeNode(Integer.parseInt(nodes[0]));
        LinkedList<TreeNode> q=new LinkedList<>();
        q.offer(root);
        for(int i=1;i<nodes.length;)
        {
            TreeNode parent=q.poll();
            String left=nodes[i++];
            if(left.equals(NULL))
                parent.left=null;
            else
            {
                parent.left=new TreeNode(Integer.parseInt(left));
                q.offer(parent.left);
            }

            String right=nodes[i++];
            if(right.equals(NULL))
                parent.right=null;
            else
            {
                parent.right=new TreeNode(Integer.parseInt(right));
                q.offer(parent.right);
            }

        }
        return root;

    }

}
//O(n)
//O(logn)  不考虑返回值的化 队列最大开销是当二叉树为满二叉树时 每层节点数最多时logn

1373. 二叉搜索子树的最大键值和

需要考虑以下问题：

1. 左右子树是否为BST
2. 左子树的最大值和右子树的最小值
3. 左右子树的节点值之和

class Solution {
    int maxSum=0;
    public int maxSumBST(TreeNode root) {
        traverse(root);
        return maxSum;
    }
    //[是否为BST,min(root),max(root),sum(root)]
    int[] traverse(TreeNode root)
    {
        if(root==null)
        {
            return new int[]{1,Integer.MAX_VALUE,Integer.MIN_VALUE,0};
        }
        //left[0]表示异root.left为根节点的二叉树是否为BST 1:是  0：不是
        //left[1]表示root.left为根节点的二叉树中的最小节点
        //left[2]表示root.left为根节点的二叉树中的最大节点
        //left[1]表示root.left为根节点的二叉树中的节点值之和
        int[] left=traverse(root.left);
        int[] right=traverse(root.right);
        int[] res=new int[4];
        if(left[0]==1&&right[0]==1&&root.val>left[2]&&root.val<right[1])//root为根节点的二叉树满足BST
        {
            res[0]=1;
            // if(root.left==null)
            // {
            //     res[1]=Math.min(root.val,left[1]);

            // }
            // else
            // {
            //     res[1]=left[1];

            // }
            // if(root.right==null)
            // {
            //     res[2]=Math.max(root.val,right[2]);

            // }
            // else
            // {
            //     res[2]=right[2];

            // }
            res[1]=Math.min(root.val,left[1]);//如果root.left!=null res[1]实际上就等于left[1]
            res[2]=Math.max(root.val,right[2]);//如果root.right!=null res[2]实际上就等于right[2]

            res[3]=root.val+left[3]+right[3];
            maxSum=Math.max(res[3],maxSum);
        }
        else
            res[0]=0;//不是BST
        return res;
    }
}
//O(n)
//o(logn)-O(n)

230. 二叉搜索树中第K小的元素

递归实现中序遍历

class Solution {
    int ans;
    int k;//要设置成成员变量 不能设置成递归函数中的参数 
    //作为参数的话由于每个栈都保存了上一级的k,因次回导致多次结果更新
    public int kthSmallest(TreeNode root, int k) {

        this.k=k;
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root)
    {
        if(root==null)
            return;
        dfs(root.left);//中序遍历 当前节点的左子树遍历完就将k--
        k--;  
        if(k==0)
        {
            ans=root.val;
            return;
        }
        dfs(root.right);    
    }
}

时间复杂度：O(H+k) 首先要遍历到最左边的叶子节点，即树的高度，然后往回回溯k次 最好情况下树是平衡二叉树，高度H=logN， 最坏情况下树退化为链表，高度H=N
空间复杂度：最好情况：O(logN) 最坏情况：O(N)

迭代实现中序遍历

//中序遍历模板
class Solution {

    public int kthSmallest(TreeNode root, int k) {

       LinkedList<TreeNode> st=new LinkedList();
       int ans=0;
       if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;// 遍历左子树，寻找最左边的子节点
                } else {// 左子节点为空，则先输出当前节点，然后开始遍历右子节点
                    root = stack.pop();
                    k--;
                    if(k==0)
                    {
                        ans=root.val;
                        break;
                    }
                    root = root.right;

                }
            }
        }
        return ans;
    }

}

时间复杂度：O(H+k) 首先要遍历到最左边的叶子节点，即树的高度，然后往回回溯k次 最好情况下树是平衡二叉树，高度H=logN， 最坏情况下树退化为链表，高度H=N
空间复杂度：最好情况：O(logN) 最坏情况：O(N)

进阶：

如果需要频繁地查找第k小的节点，则可以先用一个map记录以各个节点为根节点的子树的总节点数目，然后遍历二叉搜索树，假设当前遍历到的根节点是root, 通过map查看root的左子树有多少个节点（即以root.left为根节点的子树节点数目），记数目为num, 如果numk-1, 则说明第k小的节点在当前节点的左子树中；如果num==k-1, 则说明第k小的节点就是当前节点

class Solution {
    HashMap<TreeNode,Integer> count=new HashMap<>();
    public int kthSmallest(TreeNode root, int k) {
        calCount(root);
        while(root!=null)
        {
            //root.left可能是null 因此map中不存在 不存在返回值0
            int num=count.getOrDefault(root.left,0);
            if(num<k-1)
                {
                    root=root.right;
                    k=k-num-1;//左子树有num个节点 当前根节点1个节点
                    //所以是右子树中的第k-num-1个节点
                }
            else if(num>k-1)
                {
                    root=root.left;
                }
            else if(num==k-1)
                break;

        }
        return root.val;


    }
    public int calCount(TreeNode root)
    {
        if(root==null)
            return 0;
        //计算当前节点为根节点树的节点个数
        count.put(root,calCount(root.left)+calCount(root.right)+1);
        return count.get(root);

    }

}
//时间复杂度：O(n)  遍历每个节点

//空间复杂度：map存放每个节点 因此时间复杂度是O(n)

1038. 把二叉搜索树转换为累加树

反向中序遍历，使用一个sum记录节点的累加和

class Solution {
    int sum=0;
    public TreeNode bstToGst(TreeNode root) {
        if(root==null)
            return null;
        bstToGst(root.right);
        sum+=root.val;
        root.val=sum;//对于根节点而言，只有右子树中的节点比它大 因此累加完右子树再来处理root节点
        bstToGst(root.left);//对于左子树而言，root节点和root的右子树中的节点都比它大
        return root;
    }
}
//O(n)
//O(n)

98. 验证二叉搜索树

思路1：已知对于1棵二叉搜索树而言，对其进行中序遍历可以得到一个升序的序列，利用这种性质，使用一个变量记录前一个节点的值，然后将当前节点的值与前一个节点的值进行比较，如果小于等于的话就返回false

class Solution {
    long preVal=Long.MIN_VALUE;//因为节点的值可能取到Integer.MIN_VALUE 所以这里使用Long
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        if(isValidBST(root.left)==false)
            return false;
        if(root.val<=preVal)
            return false;
        preVal=root.val;
        if(isValidBST(root.right)==false)
            return false;
        return true;   
    }    
}
//O(n) 每个节点访问一次
//O(n) 递归调用的栈空间O(logn)-O(n)

思路2：递归，对于一棵二叉搜索树，root.left.val<roo,val<root.right.val, 需要判断每个节点构成的子树是否是BST， 但是需要注意的一点是比较不总是自己的左右子节点，而是其左子树中的最大值和右子树中的最小值

class Solution {
    public boolean isValidBST(TreeNode root) {
       return isValidBST(root,null,null);
    }   
    public boolean isValidBST(TreeNode root,TreeNode min,TreeNode max)
    {
        if(root==null)
            return true;
        if(min!=null&&root.val<=min.val)
            return false;
        if(max!=null&&root.val>=max.val)
            return false;
        //root是左子树的上界  是右子树的下界
        return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max);
    }
}
//O(n) 每个节点访问一次
//O(n) 递归调用的栈空间O(logn)-O(n)

700. 二叉搜索树中的搜索

思路1：迭代

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

          while(root!=null)
          {
              if(root.val==val)
                 break;
              else if(root.val>val)
                root=root.left;
              else if(root.val<val)
                root=root.right;
          }
          return root;
    }
}
//O(n) 最坏情况下BST是一条链
//O(1)

思路2：递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

        if(root==null)
            return null;
        if(root.val<val)
            return searchBST(root.right,val);
        else if(root.val>val)
            return searchBST(root.left,val);
        else 
            return root;

    }
}
//O(n) 最坏情况下BST是一条链
//O(n)   最坏情况下BST是一条链 递归深度达到n

701. 二叉搜索树中的插入操作

1. 迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null)
            return new TreeNode(val);
        TreeNode node=root;
        while(root!=null)
        {
            if(root.val<val)
            {
                if(root.right==null)
                {
                    root.right=new TreeNode(val);
                    break;
                }
                root=root.right;
            }
            else if(root.val>val)
            {
                if(root.left==null)
                {
                    root.left=new TreeNode(val);
                    break;

                }
                root=root.left;
            }

        }
        return node;

    }
}
//O(n) 最坏情况下BST退化为链表
//O(1)

1. 递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null)
            return new TreeNode(val);
        if(root.val<val)
            root.right=insertIntoBST(root.right,val);
        else if(root.val>val)
            root.left=insertIntoBST(root.left,val);
        return root;

    }
}
//O(n) 最坏情况下BST退化为链表
//O(n) 最坏情况下BST退化为链表

450. 删除二叉搜索树中的节点

1. 将指向即将被删除的结点的链接保存为 t
2. 将 x 指向它的后继结点 min(t.right
3. 将 x 的右链接（原本指向一棵所有结点都大于 x.key 的二叉查找树）指向 deleteMin(t.

right)，也就是在删除后所有结点仍然都大于 x.key 的子二叉查找树

1. 将 x 的左链接（本为空）设为 t.left（其下所有的键都小于被删除的结点和它的后继

结点）

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null)
            return null;
        if(root.val==key)
        {
            if(root.left==null)
                return root.right;
            if(root.right==null)
                return root.left;
            TreeNode tmp=root,tmp2=root;
            root=getMin(tmp.right);
            root.right=deleteMin(tmp.right);//1
            root.left=tmp.left;//2
            //1 2处的代码不能调换顺序 因为root=getMin(tmp.right)之后root指向的是
            //右子树中的最小节点 而root.left=tmp.left会改变右子树的结构
            //应该先删除右子树中的最小节点


        }
        else if(root.val>key)
            root.left=deleteNode(root.left,key);
        else if(root.val<key)
            root.right=deleteNode(root.right,key);
        return root;

    }
    TreeNode getMin(TreeNode node)//获取node为根节点的树中的最小值
    {
        if(node==null)
            return null;
        while(node.left!=null)
            node=node.left;
        return node;
    }
    TreeNode deleteMin(TreeNode node)//删除以node为节点的树中的最小节点
    {
        if(node.left==null)
            return node.right;
        node.left=deleteMin(node.left);
        return node;
    }
}
//O(H)  H是树的高度
//O(H)