二叉树总结篇（2）

二叉树的修改和构造

反转二叉树

迭代

class Solution {
    public TreeNode invertTree(TreeNode root) {
      if(root==null)
      return null;

      Queue<TreeNode> queue=new LinkedList<TreeNode>();
      queue.offer(root);
      while(!queue.isEmpty()){
        int len=queue.size();
        while(len>0){
            TreeNode node=queue.poll();
            len--;

            swap(node);
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);

        }
      }   

      return root;

}

public void swap(TreeNode root){
    TreeNode temp=root.left;
    root.left=root.right;
    root.right=temp;
}
}

递归

前序和后序都可以，但是中序不行

这是前序

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        swap(root);
        TreeNode left=invertTree(root.left);
        TreeNode right=invertTree(root.right);
     
        return root;
 }
   public void swap(TreeNode root){
    TreeNode temp=root.left;
    root.left=root.right;
    root.right=temp;
   }
   
}

这是后序

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;

        TreeNode left=invertTree(root.left);
        TreeNode right=invertTree(root.right);
        swap(root);
        return root;
 }
   public void swap(TreeNode root){
    TreeNode temp=root.left;
    root.left=root.right;
    root.right=temp;
   }
   
}

从中序和后序遍历序列中构造二叉树

迭代

比较复杂，意义不大

递归

这个处理方法有一个前提：二叉树中不能有重复的元素

关键：找到分割点，分割左右区间

class Solution {
    HashMap<Integer,Integer> inorderArrayMap = new HashMap<>();
    int[] post;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0;i < inorder.length; i++) {
            inorderArrayMap.put(inorder[i], i);//妙啊！将节点值及索引全部记录在哈希表中
        }
    
        post = postorder;
        TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
        return root;
    }


    public TreeNode buildTree(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
        if(inorderEnd < inorderStart || postorderEnd < postorderStart) return null;

        int root = post[postorderEnd];//根据后序遍历结果，取得根节点
        int rootIndexInInorderArray = inorderArrayMap.get(root);//获取对应的索引

        TreeNode node = new TreeNode(root);//创建该节点
        node.left = buildTree(inorderStart, rootIndexInInorderArray - 1, postorderStart, postorderStart + rootIndexInInorderArray - inorderStart - 1);
        node.right = buildTree(rootIndexInInorderArray + 1, inorderEnd, postorderStart + rootIndexInInorderArray - inorderStart, postorderEnd - 1);
        return node;//注意！返回的是新建的node！
    }
}

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

迭代

比较复杂，意义不大

递归

关键：根据前序序列找到根节点，将中序遍历的区间进行分割

难点：分割之后的区间的求法

class Solution {
    HashMap<Integer,Integer> inorderArrayMap=new HashMap<>();
    int[] pre;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
  for(int i = 0;i < inorder.length; i++) {
            inorderArrayMap.put(inorder[i], i);//妙啊！将节点值及索引全部记录在哈希表中
        }
    
        pre=preorder;
        TreeNode root = buildTree(0, inorder.length - 1, 0, pre.length - 1);
        return root;
    }


    public TreeNode buildTree(int inorderStart, int inorderEnd, int preorderStart, int preorderEnd) {
        if(inorderEnd < inorderStart || preorderEnd < preorderStart) return null;

        int root = pre[preorderStart];//根据前序遍历结果，取得根节点
        int rootIndexInInorderArray = inorderArrayMap.get(root);//获取对应的索引

        TreeNode node = new TreeNode(root);//创建该节点
        node.left = buildTree(inorderStart, rootIndexInInorderArray - 1, preorderStart+1, preorderStart+ rootIndexInInorderArray - inorderStart );
        node.right = buildTree(rootIndexInInorderArray + 1, inorderEnd, preorderStart+ rootIndexInInorderArray - inorderStart+1, preorderEnd);
        return node;//注意！返回的是新建的node！
    }
    
}

最大二叉树

迭代

比较复杂，意义不大

递归

其实递归把握的之后，真的比较简单，比迭代简单多了

关键：在数组里面找到最大值构造根节点，根据最大值的索引将数组进行区间分割，然后递归构造左子树右子树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] nums, int startIndex, int endIndex) {
        if (startIndex > endIndex) return null;
        int index = maxElementIndex(nums, startIndex, endIndex);
        \\寻找最大值对应的索引
      TreeNode newNode = new TreeNode(nums[index]);\\构造根节点
        newNode.left = build(nums, startIndex, index - 1);
        newNode.right = build(nums, index + 1, endIndex);
        return newNode;
    }

    public int maxElementIndex(int[] nums, int startIndex, int endIndex) {
        int maxIndex = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            maxIndex = nums[maxIndex] < nums[i] ? i : maxIndex;
        }
        return maxIndex;
    }
}

构造二叉树的小节：

这三道题都是构造二叉树的题目

首先关键就是找到要构造的二叉树的根节点，然后再通过递归构造根节点的左子树和右子树。

怎么找到根节点？

根据题目所给条件，比如遍历的特点，数组的特点

怎么递归构造左子树和右子树？

根据根节点的索引进行区间分割

区间分割的范围不要搞错！！！

像这样有明显规律和套路的题目使用递归比使用迭代简单多了

合并二叉树

迭代

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if(root1==null||root2==null){
        return root1==null?root2:root1;
    }
    Queue<TreeNode> queue=new LinkedList<TreeNode>();
    queue.offer(root1);
    queue.offer(root2);
    while(!queue.isEmpty()){
        int len=queue.size();
        TreeNode t1=queue.poll();
        TreeNode t2=queue.poll();
        t1.val+=t2.val;
       
        if(t1.left!=null&&t2.left!=null){
            queue.offer(t1.left);
            queue.offer(t2.left);

        }else if(t1.left==null){
            t1.left=t2.left;
        }

        if(t1.right!=null&&t2.right!=null){
            queue.offer(t1.right);
            queue.offer(t2.right);

        }else if(t1.right==null){
            t1.right=t2.right;
        }

    }
    return root1;
    }
}

递归

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if(root1==null||root2==null){
        return root1==null?root2:root1;
    }
    return  dfs(root1,root2);
    }
    public TreeNode dfs(TreeNode root1, TreeNode root2){
         if(root1==null||root2==null){
        return root1==null?root2:root1;
        }

        root1.val+=root2.val;
        root1.left=dfs(root1.left,root2.left);
        root1.right=dfs(root1.right,root2.right);
        return root1;
    }
}

二叉搜索树的属性

二叉搜素树中的搜索

迭代

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null && root.val != val) {
            root = root.val < val ? root.right : root.left;
        }
        return root;
    }
}

递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
      if(root==null||root.val==val) return root;
      if(root.val>val) return searchBST(root.left,val);
      return searchBST(root.right,val);
    }
}

是不是二叉搜索树

迭代

引入栈

class Solution {
    // 迭代
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;// 左
            }
            // 中，处理
            TreeNode pop = stack.pop();
            if (pre != null && pop.val <= pre.val) {
                return false;
            }
            pre = pop;

            root = pop.right;// 右
        }
        return true;
    }
}

递归

关键：判断是否是二叉搜索树，必须满足其性质，所以就是要检验每个节点是否在左右范围区间内，所以左区间，右区间作为参数传递进去

这种思路比题解的pre的思路其实是一样，但是更直观更好理解

class Solution {
    public boolean isValidBST(TreeNode root) {
    if(root==null) return true;

    return deal(root,Long.MAX_VALUE,Long.MIN_VALUE);
   }
    public boolean deal(TreeNode root,long max,long min){
        if(root==null) return true;
       

       if(root.val<=min||root.val>=max) return false;

       return deal(root.left,root.val,min)&&deal(root.right,max,root.val);
      

    }
}

二叉搜索树的最小绝对差

迭代

// 迭代法-中序遍历
class Solution {
    TreeNode pre;
    Stack<TreeNode> stack;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        stack = new Stack<>();
        TreeNode cur = root;
        int result = Integer.MAX_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur); // 将访问的节点放进栈
                cur = cur.left; // 左
            }else {
                cur = stack.pop(); 
                if (pre != null) { // 中
                    result = Math.min(result, cur.val - pre.val);
                }
                pre = cur;
                cur = cur.right; // 右
            }
        }
        return result;
    }
}

递归

二叉搜索树和中序遍历息息相关，二叉搜索树经过中序遍历一个有序序列，求最小绝对差就是求相邻元素的差值最小的一个

class Solution {
    int min=Integer.MAX_VALUE;
    int pre=Integer.MIN_VALUE;
    public int getMinimumDifference(TreeNode root) {
        
        min(root);
        return min;
     }
     public void min(TreeNode root){
        if(root==null) return ;
      
      min(root.left);
        if(pre!=Integer.MIN_VALUE){
            min=Math.min(min,Math.abs(root.val-pre));
        }
        pre=root.val;
  
        min(root.right);
     }
}

求二叉搜索树的众数

递归

class Solution {
    int maxCount = 1;//元素出现最大的次数
    int count = 1;//每一个元素出现的次数
    TreeNode preNode = null;    // 存储前一个结点
    List<Integer> list = new ArrayList();   // 结果集
    public int[] findMode(TreeNode root) {
        // 中序遍历中，相同的元素都是一起出现的
        inOrder(root);
        int res[] = new int[list.size()];
        for(int i=0;i<list.size();i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void inOrder(TreeNode root) {
        if(root == null) return ;
        inOrder(root.left);

        // 中序遍历的处理逻辑
        if(preNode!=null) {  // 非第一个元素的处理逻辑
            // 判断当前元素与前一个元素的关系，如果相同count++,不相同重新开始计数
            if(root.val==preNode.val) count++;
            else count=1;
            // 判断当前计数器与最大数的关系，如果相等就加入list，大于就清空list并加入
            if(count>maxCount) {
                maxCount = count;
                list.clear();
                list.add(root.val);
            } else if(count==maxCount) 
                list.add(root.val);
        
        } else list.add(root.val);     // 第一个元素的处理逻辑，直接加入list
        // 指向前一个元素
        preNode = root;

        inOrder(root.right);
    }
}

将二叉搜索树转换成累加树

迭代

借助栈

class Solution {
    public TreeNode convertBST(TreeNode root) {
        TreeNode cur;
        int sum = 0;
        Stack<TreeNode> s = new Stack<TreeNode>();
        for (cur = root; cur != null; cur = cur.right)
            s.add(cur);
        while (!s.empty()){
            cur = s.pop();
            sum += cur.val;
            cur.val = sum;
            for (cur = cur.left; cur != null; cur = cur.right)
                s.add(cur);
        }
        return root;
    }
}

递归

由于题目要求是将大于等于的值加到一起放进去，所以对中序遍历修改成“右中左”的顺序

class Solution {
    int tot=0;
    public TreeNode convertBST(TreeNode root) {
    dfs(root);
    return root;
    }
    public void dfs(TreeNode root){
        if(root==null) return ;
        dfs(root.right);
        tot+=root.val;
        root.val=tot;
        dfs(root.left);
        
    }
}

二叉树的公共祖先问题

二叉树的公共祖先问题

迭代

不适合

递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||p==root||q==root) 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;

    }
}

二叉搜索树的最近公共祖先

迭代

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if (root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}

递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       
            if(root.val>p.val&&root.val>q.val)
               return lowestCommonAncestor(root.left,p,q);
             if(root.val<p.val&&root.val<q.val)
                return lowestCommonAncestor(root.right,p,q);
         
       
        return root;
    }
}

二叉搜索树的修改与构造

二叉搜索树的插入操作

迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            return node;
        }

        TreeNode cur = root;
        while (true) {
            if (cur.val > val) {
                if (cur.left == null) {
                    cur.left = node;
                    break;
                }
                cur = cur.left;
            } else {
                if (cur.right == null) {
                    cur.right = node;
                    break;
                } 
                cur = cur.right;
            }
        }
        return root;
    }
}

递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
    
     if(root==null) return new TreeNode(val);

     if(root.val>val)
     root.left=insertIntoBST(root.left,val);
     else
     root.right=insertIntoBST(root.right,val);
     

return root;

    }
}

删除二叉搜索树中的节点

迭代

复杂

递归

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 cur=root.left;
       while(cur.right!=null) cur=cur.right;//这一步利用二叉搜索树的性质是找到左子树的最大值
       cur.right=root.right;
       return root.left;
    } else if(root.val>key) root.left=deleteNode(root.left,key);
      else root.right=deleteNode(root.right,key);
        return root;
    
    }

}

修改二叉搜索树

迭代

复杂

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
    while(root!=null&&(root.val>high||root.val<low)) 
    root=root.val>high?root.left:root.right;
     
      TreeNode t=root;
        while(root!=null){
        while(root.left!=null&&root.left.val<low) root.left=root.left.right;
            root=root.left;
        }
        root=t;
        while(root!=null){
        while(root.right!=null&&root.right.val>high) root.right=root.right.left;
            root=root.right;
        }
   
    return t;
    }
        }
  

递归

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
    if(root==null) return null;
    if(root.val<low) return trimBST(root.right,low,high);
    else if(root.val>high) return trimBST(root.left,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) {
      return dfs(nums,0,nums.length-1);

    }
    public TreeNode dfs(int[] nums,int l,int h){
        if(l>h){
            return null;
        }
        int m=l+(h-l)/2;
        TreeNode root=new TreeNode(nums[m]);
        root.left=dfs(nums,l,m-1);
        root.right=dfs(nums,m+1,h);
        return root;
    }
}