• 数据结构与算法------二叉树

    二叉树的递归遍历(前-中-后序)

    1. // 前序遍历·递归·LC144_二叉树的前序遍历
    2. class Solution {
    3.     public List preorderTraversal(TreeNode root) {
    4.         List result = new ArrayList();
    5.         preorder(root, result);
    6.         return result;
    7.     }
    8.  
    9.     public void preorder(TreeNode root, List result) {
    10.         if (root == null) {
    11.             return;
    12.         }
    13.         result.add(root.val);
    14.         preorder(root.left, result);
    15.         preorder(root.right, result);
    16.     }
    17. }
    18. // 中序遍历·递归·LC94_二叉树的中序遍历
    19. class Solution {
    20.     public List inorderTraversal(TreeNode root) {
    21.         List res = new ArrayList<>();
    22.         inorder(root, res);
    23.         return res;
    24.     }
    25.  
    26.     void inorder(TreeNode root, List list) {
    27.         if (root == null) {
    28.             return;
    29.         }
    30.         inorder(root.left, list);
    31.         list.add(root.val);             // 注意这一句
    32.         inorder(root.right, list);
    33.     }
    34. }
    35. // 后序遍历·递归·LC145_二叉树的后序遍历
    36. class Solution {
    37.     public List postorderTraversal(TreeNode root) {
    38.         List res = new ArrayList<>();
    39.         postorder(root, res);
    40.         return res;
    41.     }
    42.  
    43.     void postorder(TreeNode root, List list) {
    44.         if (root == null) {
    45.             return;
    46.         }
    47.         postorder(root.left, list);
    48.         postorder(root.right, list);
    49.         list.add(root.val);             // 注意这一句
    50.     }
    51. }

    二叉树的层次遍历( BFS--迭代方式--借助队列)

    1.  //BFS--迭代方式--借助队列
    2. class Solution {
    3.     public List> resList = new ArrayList>();
    4.  
    5.     public List> levelOrder(TreeNode root) {
    6.         checkFun(root);
    7.         return resList;
    8.     }
    9.  
    10.     //BFS--迭代方式--借助队列
    11.     public void checkFun(TreeNode node) {
    12.         if (node == null) return;
    13.         Queue que = new LinkedList();
    14.         que.offer(node);
    15.  
    16.         while (!que.isEmpty()) {
    17.             List itemList = new ArrayList();
    18.             int len = que.size();
    19.  
    20.             while (len > 0) {
    21.                 TreeNode tmpNode = que.poll();
    22.                 itemList.add(tmpNode.val);
    23.  
    24.                 if (tmpNode.left != null) que.offer(tmpNode.left);
    25.                 if (tmpNode.right != null) que.offer(tmpNode.right);
    26.                 len--;
    27.             }
    28.  
    29.             resList.add(itemList);
    30.         }
    31.     }
    32. }

    226. 翻转二叉树

    给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

    示例 1：

    输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

    示例 2：

    输入：root = [2,1,3]
输出：[2,3,1]

    示例 3：

    输入：root = []
输出：[]

    1. //DFS--递归
    2. class Solution {
    3.      public TreeNode invertTree(TreeNode root) {
    4.         if(root==null) return root;
    5.  
    6.         TreeNode left=invertTree(root.left);
    7.         TreeNode right=invertTree(root.right);
    8.         swap(root);
    9.  
    10.         return root;
    11.     }
    12.  
    13.     //交换
    14.     public void swap(TreeNode root){
    15.         TreeNode temp=root.left;
    16.         root.left=root.right;
    17.         root.right=temp;
    18.     }
    19. }
    20.  
    21. //BFS--层次遍历
    22. class Solution {
    23.      public TreeNode invertTree(TreeNode root) {
    24.         if(root==null) return null;
    25.     
    26.         Queue queue=new LinkedList<>();
    27.         queue.offer(root);
    28.  
    29.         while(!queue.isEmpty()){
    30.             int size=queue.size();
    31.  
    32.             while(size-->0){
    33.                 TreeNode node = queue.poll();
    34.                 swap(node);
    35.                 
    36.                 if(node.left!=null) queue.offer(node.left);
    37.                 if(node.right!=null) queue.offer(node.right);
    38.             }
    39.         } 
    40.         return root;
    41.     }
    42.  
    43.      public void swap(TreeNode root){
    44.         TreeNode temp=root.left;
    45.         root.left=root.right;
    46.         root.right=temp;
    47.      }
    48. }

     101. 对称二叉树

    给你一个二叉树的根节点 root ， 检查它是否轴对称。

    示例 1：

    输入：root = [1,2,2,3,4,4,3]
输出：true

    示例 2：

    输入：root = [1,2,2,null,3,null,3]
输出：false
    1. //DFS--递归
    2. class Solution {
    3.     public boolean isSymmetric(TreeNode root) {
    4.         return compare(root.left,root.right);
    5.     }
    6.  
    7.     public boolean compare(TreeNode left,TreeNode right){
    8.         if(left==null&&right!=null) return false;
    9.  
    10.         if(right==null&&left!=null) return false;
    11.  
    12.         if(left==null&&right==null) return true;
    13.  
    14.         if(left.val!=right.val) return false;
    15.  
    16.         return compare(left.left,right.right)&&compare(left.right,right.left);
    17.     }
    18. }
    19.  
    20. //BFS--层次 队列
    21. class Solution {
    22.     public boolean isSymmetric(TreeNode root) {
    23.         if(root==null) return true;
    24.  
    25.         Queue queue=new LinkedList<>();
    26.         queue.offer(root.left);
    27.         queue.offer(root.right);
    28.  
    29.         while(!queue.isEmpty()){
    30.             int size=queue.size();
    31.  
    32.             while(size-->0){
    33.                 TreeNode left=queue.poll();
    34.                 TreeNode right=queue.poll();
    35.                
    36.                 
    37.  
    38.                 if(left==null&&right!=null) return false;
    39.  
    40.                 if(left!=null&&right==null) return false;
    41.  
    42.                 if(left==null&&right==null) continue;
    43.  
    44.                 if(left.val!=right.val) return false;
    45.  
    46.                 
    47.                  queue.offer(left.left);
    48.                  queue.offer(right.right);
    49.                  queue.offer(left.right);
    50.                  queue.offer(right.left);
    51.                
    52.             }
    53.         }
    54.         return true;
    55.     }
    56. }

    111. 二叉树的最小深度

    给定一个二叉树，找出其最小深度。

    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

    说明：叶子节点是指没有子节点的节点。

    示例 1：

    输入：root = [3,9,20,null,null,15,7]
输出：2

    示例 2：

    输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
    1. //递归
    2. class Solution {
    3.     public int minDepth(TreeNode root) {
    4.         if(root==null) return 0;
    5.         int res=0;
    6.  
    7.         int leftDepth=minDepth(root.left);
    8.         int rightDepth=minDepth(root.right);
    9.  
    10.         if(root.left==null&&root.right!=null){
    11.             return rightDepth+1;
    12.         }
    13.  
    14.         if(root.left!=null&&root.right==null){
    15.             return leftDepth+1;
    16.         }
    17.  
    18.        
    19.         
    20.         res=Math.min(leftDepth,rightDepth)+1;
    21.         return res;
    22.     }
    23. }
    24.  
    25. //BFS 队列
    26. class Solution {
    27.     public int minDepth(TreeNode root) {
    28.         if(root==null) return 0;
    29.  
    30.         Queue queue=new LinkedList<>();
    31.         queue.offer(root);
    32.         int depth=0;
    33.         while(!queue.isEmpty()){
    34.             int size=queue.size();
    35.             depth++;
    36.             while(size-->0){
    37.             
    38.                 TreeNode node=queue.poll();
    39.                      
    40.              
    41.                 if(node.left!=null) queue.offer(node.left);
    42.                 if(node.right!=null) queue.offer(node.right);    
    43.                 if(node.left==null&&node.right==null) return depth;        
    44.             }
    45.         }
    46.         return depth;
    47.     }
    48. }

    222. 完全二叉树的节点个数

    给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

    完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

    1. //递归
    2. class Solution {
    3.     public int countNodes(TreeNode root) {
    4.         if(root==null) return 0;
    5.         int res=0;
    6.  
    7.         if(root.left!=null){
    8.             res+=countNodes(root.left);
    9.         }
    10.  
    11.         if(root.right!=null){
    12.             res+=countNodes(root.right);
    13.         }
    14.  
    15.         return res+1;
    16.     }
    17. }
    18.  
    19. //BFS
    20. class Solution {
    21.     public int countNodes(TreeNode root) {
    22.         if(root==null) return 0;
    23.  
    24.         Queue queue=new LinkedList<>();
    25.         queue.offer(root);
    26.         int res=0;
    27.         while(!queue.isEmpty()){
    28.             int size=queue.size();
    29.             while(size-->0){
    30.                 TreeNode node=queue.poll();
    31.                  res++;
    32.                 if(node.left!=null) queue.offer(node.left);
    33.                 if(node.right!=null) queue.offer(node.right);
    34.             }
    35.         }
    36.         return res;
    37.     }    
    38. }

    示例 1：

    输入：root = [1,2,3,4,5,6]
输出：6

    示例 2：

    输入：root = []
输出：0

    示例 3：

    输入：root = [1]
输出：1

     110. 平衡二叉树

    给定一个二叉树，判断它是否是高度平衡的二叉树。

    本题中，一棵高度平衡二叉树定义为：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 

    示例 1：

    输入：root = [3,9,20,null,null,15,7]
输出：true

    示例 2：

    输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

    示例 3：

    输入：root = []
输出：true

    1.  //递归
    2. class Solution {
    3.     public boolean isBalanced(TreeNode root) {
    4.         if(root==null) return true;
    5.  
    6.         int left=hight(root.left);
    7.         int right=hight(root.right);
    8.         
    9.         if(Math.abs(right-left)>1){
    10.             return false;
    11.         }
    12.         return isBalanced(root.left)&&isBalanced(root.right);
    13.     }
    14.     //递归求高度
    15.     public int hight(TreeNode root){
    16.         if(root==null) return 0;
    17.  
    18.         return Math.max(hight(root.left),hight(root.right))+1;
    19.     }
    20. }
    21.  
    22. //BFS求高度
    23. public int hight(TreeNode root){
    24.     if(root==null) return 0;
    25.  
    26.     Queue node = new LinkedList<>();
    27.     queue.offer(root);
    28.     int res=0;
    29.     while(!queue.isEmpty()){
    30.         int size=queue.size();
    31.         res++;
    32.         while(size-->0){
    33.             TreeNode node=queue.poll();
    34.             if(node.left!=null) queue.offer(node.left);
    35.             if(node.right!=null) queue.offer(node.right);
    36.         }
    37.     }
    38.     return res;
    39. }

    257. 二叉树的所有路径

    给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

    叶子节点 是指没有子节点的节点。

    示例 1：

    输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

    示例 2：

    输入：root = [1]
输出：["1"]
    1. class Solution {
    2.     public List binaryTreePaths(TreeNode root) {
    3.         List res=new LinkedList<>();    
    4.         List path=new LinkedList<>();
    5.         
    6.         getPath(root,res,path);
    7.  
    8.         return res;
    9.     }
    10.  
    11.     public void getPath(TreeNode root,List res,List path){
    12.         if(root==null) return;
    13.         path.add(root.val);
    14.  
    15.         
    16.         if(root.left==null&&root.right==null){//叶子节点
    17.             StringBuilder sb=new StringBuilder();
    18.             for(int i=0;i1;i++){
    19.                 
    20.                 sb.append(path.get(i)).append("->");
    21.             }
    22.                 sb.append(path.get(path.size()-1));//处理最后一个节点
    23.                 res.add(sb.toString());
    24.         }
    25.         
    26.         if(root.left!=null){
    27.             getPath(root.left,res,path);
    28.             path.remove(path.size()-1);
    29.         }
    30.  
    31.         if(root.right!=null){
    32.             getPath(root.right,res,path);
    33.             path.remove(path.size()-1);
    34.         }
    35.     }
    36. }

    404. 左叶子之和

    给定二叉树的根节点 root ，返回所有左叶子之和。

    示例 1：

    转存失败重新上传取消

    输入: root = [3,9,20,null,null,15,7] 
    输出: 24 
    解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

    示例 2:

    输入: root = [1]
输出: 0
    1. //DFS 递归
    2. class Solution {
    3.      public int sumOfLeftLeaves(TreeNode root) {
    4.         if(root==null) return 0;
    5.  
    6.         int left=sumOfLeftLeaves(root.left);
    7.         int right=sumOfLeftLeaves(root.right);
    8.  
    9.         int value=0;
    10.         if(root.left!=null&&root.left.left==null&&root.left.right==null){
    11.             value+=root.left.val;
    12.         }
    13.         int res=left+right+value;
    14.  
    15.         return res;
    16.     }
    17. }
    18.  
    19. //BFS 层次 队列
    20. class Solution {
    21.     public int sumOfLeftLeaves(TreeNode root) {
    22.         if(root==null || root.left==null&&root.right==null) return 0;
    23.  
    24.         Queue queue=new LinkedList<>();
    25.         queue.offer(root);
    26.         int sum=0;
    27.         while(!queue.isEmpty()){
    28.             int size=queue.size();
    29.             while(size-->0){
    30.                 TreeNode node=queue.poll();
    31.              
    32.                 if(node.left!=null) {
    33.                     if(node.left.left==null&&node.left.right==null){
    34.                         sum+=node.left.val;
    35.                     }
    36.                     queue.offer(node.left);
    37.                 }
    38.                 if(node.right!=null){
    39.                     queue.offer(node.right);
    40.                 }
    41.             }
    42.         }
    43.         return sum;
    44.     }
    45. }

    这题在层次遍历中出错，直接在node.left!=null里面判断是左叶子就行 

    这题关键点是：1.找左叶子 2.左叶子的判断是root.left!=null&&root.left.left==null&&root.left.right==null

    513. 找树左下角的值

    给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

    假设二叉树中至少有一个节点。

    示例 1:

    输入: root = [2,1,3]
输出: 1

    示例 2:

    输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
    1. // 递归法
    2. class Solution {
    3.     private int Deep = -1;
    4.     private int value = 0;
    5.     public int findBottomLeftValue(TreeNode root) {
    6.         value = root.val;
    7.         findLeftValue(root,0);
    8.         return value;
    9.     }
    10.  
    11.     private void findLeftValue (TreeNode root,int deep) {
    12.         if (root == null) return;
    13.         if (root.left == null && root.right == null) {//到叶子节点
    14.             if (deep > Deep) {
    15.                 value = root.val;
    16.                 Deep = deep;//到最大深度
    17.             }
    18.         }
    19.         findLeftValue(root.left,deep + 1);
    20.         findLeftValue(root.right,deep + 1);
    21.     }
    22. }
    23. //BFS 层次
    24. class Solution {
    25.     public int findBottomLeftValue(TreeNode root) {
    26.         if(root==null) return 0;
    27.         if(root.left==null&&root.right==null) return root.val;
    28.         Queue queue=new LinkedList<>();
    29.         queue.offer(root);
    30.         int res=0;
    31.         while(!queue.isEmpty()){
    32.             int size=queue.size();
    33.             while(size-->0){
    34.                 TreeNode node=queue.poll();
    35.                 if(size==0) res=node.val;
    36.                 
    37.                 if(node.right!=null) {
    38.                     queue.offer(node.right);
    39.                 }
    40.                  if(node.left!=null) {
    41.                     queue.offer(node.left);
    42.                 }
    43.             }
    44.         }
    45.         return res;
    46.     }
    47. }

    本题递归需要注意的是：1 先找叶子节点 2 找最大深度  层次遍历只需要每次更新size=0即最左边的节点的值

    112. 路径总和

    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

    叶子节点 是指没有子节点的节点。

    示例 1：

    输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    输出：true
    解释：等于目标和的根节点到叶节点路径如上图所示。

    示例 2：

    输入：root = [1,2,3], targetSum = 5
    输出：false
    解释：树中存在两条根节点到叶子节点的路径：
    (1 --> 2): 和为 3
    (1 --> 3): 和为 4
    不存在 sum = 5 的根节点到叶子节点的路径。
    示例 3：

    输入：root = [], targetSum = 0
    输出：false
    解释：由于树是空的，所以不存在根节点到叶子节点的路径。

    1. class Solution {
    2.     public boolean hasPathSum(TreeNode root, int targetSum) {
    3.         if(root==null) return false;
    4.  
    5.         targetSum-=root.val;
    6.  
    7.         if(root.left==null&&root.right==null&&targetSum==0) return true;
    8.  
    9.         if(root.left!=null) {
    10.             if(hasPathSum(root.left,targetSum))
    11.             return true;
    12.         }
    13.  
    14.         if(root.right!=null){
    15.             if(hasPathSum(root.right,targetSum))
    16.             return true;
    17.         }
    18.  
    19.         return false;
    20.     }
    21. }
    1. class Solution {
    2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
    3.         if(inorder.length==0 || postorder.length==0) return null;
    4.  
    5.         return build(inorder,0,inorder.length,postorder,0,postorder.length);
    6.     }
    7.  
    8.     public TreeNode build(int[] inorder,int inorderLeft,int inorderRight,int[] postorder,int posLeft,int posRight){
    9.  
    10.         
    11.         int rootValue=postorder[postRight-1];//找到后序节点的尾节点 该节点为原树的头节点
    12.         TreeNode root=new TreeNode(rootValue);//构造头节点
    13.  
    14.         int rootIndex=0;
    15.         for(int i=inorderLeft;i//在中序中找到分割点
    16.             if(rootValue==inorder[i]){
    17.                 rootIndex=i;
    18.                 break;
    19.             }
    20.         }
    21.         //递归
    22.         root.left=build(inorder,inorderLeft,rootInex,postorder,posLeft,posLeft+(rootIndex-inorderLeft));
    23.         root.right=build(inorder,rootIndex+1,inorderRight,postorder,posLeft+(rootIndex-1),posRight);
    24.     }
    25. }

    654. 最大二叉树

    给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

    创建一个根节点，其值为 nums 中的最大值。
    递归地在最大值 左边 的 子数组前缀上 构建左子树。
    递归地在最大值 右边 的 子数组后缀上 构建右子树。
    返回 nums 构建的 最大二叉树 。

    示例 1：

    输入：nums = [3,2,1,6,0,5]
    输出：[6,3,5,null,2,0,null,null,1]
    解释：递归调用如下所示：
    - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
        - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
            - 空数组，无子节点。
            - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
                - 空数组，无子节点。
                - 只有一个元素，所以子节点是一个值为 1 的节点。
        - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
            - 只有一个元素，所以子节点是一个值为 0 的节点。
            - 空数组，无子节点。

    示例 2：

    输入：nums = [3,2,1]
输出：[3,null,2,null,1]

    1. class Solution {
    2.     public TreeNode constructMaximumBinaryTree(int[] nums) {
    3.         if(nums.length==0) return null;
    4.  
    5.         return build(nums,0,nums.length);
    6.     }
    7.  
    8.     public TreeNode build(int[] nums,int left,int right){
    9.         if(right-left<1) return null;
    10.  
    11.         if(right-left==1) return new TreeNode(nums[left]);
    12.  
    13.         int rootValue=0;
    14.         int rootIndex=0;
    15.     
    16.         for(int i=0;i
    17.             if(nums[i]>rootValue){
    18.                 rootValue=nums[i];
    19.                 rootIndex=i;
    20.             }
    21.         }
    22.  
    23.         TreeNode root=new TreeNode(rootValue);
    24.  
    25.         root.left=build(nums,left,rootIndex);
    26.         root.right=build(nums,rootIndex+1,right);
    27.  
    28.         return root;
    29.     } 
    30. }

    617. 合并二叉树

    给你两棵二叉树： root1 和 root2 。

    想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

    返回合并后的二叉树。

    示例 1：

    输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
    输出：[3,4,5,5,4,null,7]
    示例 2：

    输入：root1 = [1], root2 = [1,2]
    输出：[2,2]

    1. class Solution {
    2.     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    3.         if(root1==null&&root2==null) return null;
    4.  
    5.         if(root1==null&&root2!=null) return root2;//root2不为空 返回root2
    6.  
    7.         if(root1!=null&&root2==null) return root1;//root1不为空 返回root2
    8.  
    9.         TreeNode root=new TreeNode(root1.val+root2.val);//创建新的节点
    10.  
    11.         root.left=mergeTrees(root1.left,root2.left);//合并左节点
    12.         root.right=mergeTrees(root1.right,root2.right);//合并右节点
    13.  
    14.         return root;
    15.     }
    16. }

    700. 二叉搜索树中的搜索

    给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

    你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

    示例 1:

    输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

    示例 2:

    输入：root = [4,2,7,1,3], val = 5
输出：[]

    1. //利用二叉搜索树的性质
    2. class Solution {
    3.      public TreeNode searchBST(TreeNode root, int val) {
    4.         if(root==null) return null;
    5.  
    6.         if(root.val==val) return root;
    7.  
    8.         if(val
    9.             return searchBST(root.left,val);
    10.         }else if(val>root.val){
    11.              return searchBST(root.right,val);
    12.         }
    13.  
    14.         return root;
    15.     }
    16. }

    98. 验证二叉搜索树

    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

    有效 二叉搜索树定义如下：

    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

    示例 1：

    输入：root = [2,1,3]
输出：true

    1. class Solution {
    2.     public boolean isValidBST(TreeNode root) {
    3.        return isBST(root,null,null);
    4.     }
    5.     public boolean isBST(TreeNode root,TreeNode min,TreeNode max){
    6.         if(root==null) return true;
    7.  
    8.         if(min!=null&&root.val<=min.val) return false;
    9.         if(max!=null&&root.val>=max.val) return false;
    10.  
    11.         return isBST(root.left,min,root)&&isBST(root.right,root,max);
    12.     }
    13. }

    530. 二叉搜索树的最小绝对差

    给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

    差值是一个正数，其数值等于两值之差的绝对值。

    示例 1：

    输入：root = [4,2,6,1,3]
输出：1 

    示例 2：

    输入：root = [1,0,48,null,null,12,49]
输出：1

    注意：如果出现二叉搜索树求最值，差值之类的，把它转化成有序数组，然后中序遍历

    1. class Solution {
    2.     TreeNode pre;
    3.     int res=Integer.MAX_VALUE;
    4.     public int getMinimumDifference(TreeNode root) {
    5.         if(root==null) return 0;
    6.  
    7.         traval(root);
    8.  
    9.         return res;
    10.     }
    11.  
    12.     public void traval(TreeNode root){
    13.         if(root==null) return;
    14.  
    15.         traval(root.left);
    16.  
    17.         if(pre!=null){
    18.             res=Math.min(res,root.val-pre.val);
    19.         }
    20.  
    21.         pre=root;
    22.  
    23.         traval(root.right);
    24.     }
    25. }

    236. 二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    示例 1：

    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出：3
    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

    示例 2：

    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出：5
    解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

    1. class Solution {
    2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.         if(root==null || root==p || root==q) return root;
    4.  
    5.         TreeNode left=lowestCommonAncestor(root.left,p,q);
    6.         TreeNode right=lowestCommonAncestor(root.right,p,q);
    7.  
    8.         if(left==null&&right==null) return null;
    9.         if(left==null && right!=null) return right;
    10.         if(left!=null && right==null) return left;
    11.  
    12.         return root;
    13.     }
    14. }

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

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    示例 1:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

    示例 2:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

    1. class Solution {
    2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.         if(root==null || root==p || root==q) return root;
    4.  
    5.         TreeNode left=lowestCommonAncestor(root.left,p,q);
    6.         TreeNode right=lowestCommonAncestor(root.right,p,q);
    7.  
    8.         if(root.valreturn left;
    9.         if(root.val>p.val&&root.val>q.val) return right;
    10.  
    11.         return root;
    12.     }
    13. }

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

    给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

    注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

    示例 1：

    输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

    示例 2：

    输入：root = [40,20,60,10,30,50,70], val = 25
    输出：[40,20,60,10,30,50,70,null,null,25]

    示例 3：

    输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
    输出：[4,2,7,1,3,5]

    1. class Solution {
    2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3.         if(root==null) return new TreeNode(val);
    4.  
    5.        
    6.         if(root.val>val) root.left=insertIntoBST(root.left,val);
    7.         if(root.val
    8.  
    9.         return root;
    10.     }
    11. }

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

    给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

    一般来说，删除节点可分为两个步骤：

    首先找到需要删除的节点；
    如果找到了，删除它。

    示例 1:

    输入：root = [5,3,6,2,4,null,7], key = 3
    输出：[5,4,6,2,null,null,7]
    解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
    一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
    另一个正确答案是 [5,2,6,null,4,null,7]。

    示例 2:

    输入: root = [5,3,6,2,4,null,7], key = 0
    输出: [5,3,6,2,4,null,7]
    解释: 二叉树不包含值为 0 的节点
    示例 3:

    输入: root = [], key = 0
    输出: []

    1. class Solution {
    2.      public TreeNode deleteNode(TreeNode root, int key) {
    3.          if(root==null) return null;
    4.          if(root.val==key){
    5.              if(root.left==null){
    6.                  return root.right;
    7.              }else if(root.right==null){
    8.                  return root.left;
    9.              }else{
    10.                  TreeNode cur=root.right;
    11.                  while(cur.left!=null){
    12.                      cur=cur.left;
    13.                  }
    14.                  cur.left=root.left;
    15.                  root=root.right;
    16.                  return root;
    17.              }
    18.          }
    19.          if(root.val>key) root.left=deleteNode(root.left,key);
    20.          if(root.val
    21.  
    22.          return root;
    23.  
    24.      }
    25. }

    669. 修剪二叉搜索树 

    给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

    所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

    示例 1：

    输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

    示例 2：

    输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
    1. class Solution {
    2.     public TreeNode trimBST(TreeNode root, int low, int high) {
    3.         if(root==null) return null;
    4.  
    5.         if(root.val>low){
    6.             TreeNode left=trimBST(root.left,low,high);//寻找符合区间
    7.             return left;
    8.         }
    9.  
    10.         if(root.val
    11.             TreeNode right=trimBST(root.right,low,high);//寻找符合区间
    12.             return right;
    13.         }
    14.  
    15.         root.left=trimBST(root.left,low,high);
    16.         root.right=trimBST(root.right,low,high);
    17.  
    18.         return root;
    19.     }
    20. }

    108. 将有序数组转换为二叉搜索树 

    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

    高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

    示例 1：

    输入：nums = [-10,-3,0,5,9]
    输出：[0,-3,9,-10,null,5]
    解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

    示例 2：

     

     

    输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

    1. class Solution {
    2.     public TreeNode sortedArrayToBST(int[] nums) {
    3.         if(nums.length==0) return null;
    4.         return travel(nums,0,nums.length-1);
    5.         
    6.     }
    7.  
    8.     public TreeNode travel(int[] nums,int left,int right){
    9.         if(left>right) return null;
    10.         int mid=left+(right-left)/2;
    11.         TreeNode root=new TreeNode(nums[mid]);//构造头节点
    12.  
    13.         root.left=travel(nums,left,mid-1);//构造左节点
    14.         root.right=travel(nums,mid+1,right);//构造右节点
    15.  
    16.         return root;
    17.     }
    18. }

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

    给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

     

    示例 1：

    输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
    输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

    示例 2：

    输入：root = [0,null,1]
    输出：[1,null,1]
    示例 3：

    输入：root = [1,0,2]
    输出：[3,3,2]
    示例 4：

    输入：root = [3,2,4,1]
    输出：[7,9,4,10]

    思路：采用中序遍历的逆序，也就是右中左的顺序

    1. class Solution {
    2.     int pre=0;
    3.     public TreeNode convertBST(TreeNode root) {
    4.         return travel(root);
    5.     }
    6.  
    7.     public TreeNode travel(TreeNode root){
    8.         if(root==null) null;
    9.  
    10.         travel(root.right);//右
    11.  
    12.         root.val+=pre;//中
    13.         pre=root.val;
    14.  
    15.         travel(root.left);//左
    16.  
    17.         return root;
    18.     }
    19. }

     

     

     

  • 相关阅读:
    在Win11的子系统中安装 Ubuntu ，并安装DotNet
    mongodb
    JUC 笔记 8
    C++入门及简单例子_4
    【 Git 】 Merge or Rebase
    正则表达式转换为相应的文字小工具
    评价——层次分析
    基于ssm+mysql+jsp作业管理(在线学习)系统
    学习响应式布局
    Linux企业运维之git的使用
  • 原文地址：https://blog.csdn.net/weixin_46345400/article/details/125986153