• 二叉树的搜索与回溯问题(leetcode)

    1.力扣_二叉树中和为某一值的路径

            给你二叉树的根节点 root和一个整数目标和targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

    思路 : 深度优先搜索，进行递归遍历即可解决（回溯法）

            分先序遍历+路径记录两部分

            先序遍历：根左右顺序遍历二叉树所有节点

            路径记录：在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径且② 各节点值的和等于目标值target时，将此路径加入结果列表

            递归函数：

            1）递推参数：当前节点 root，当前目标值target
            2）终止条件：若节点root为空，则直接返回
            3）递推工作：
            a.路径更新： 将当前节点值 root.val 加入路径 path ；
            b.目标值更新：target=target-root.val（即目标值target减至0）；
            c.路径记录：当 ① root 为叶子节点 且 ② 路径和等于目标值 ，则将此路径path加入res 
            d.先序遍历：递归左 / 右子节点。
            e.路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop()

    注意：将路径假如结果集中时，不能直接加入。因为若直接执行 res.append(path)，则是将path对象加入了res；后续path改变时，res中的path对象也会随之改变。

            正确写法：res.append(list(path)) ，相当于复制了一个path并加入到 res

    1. public class Num34_二叉树中和为某一值的路径 {
    2.     private class TreeNode {
    3.       int val;
    4.       TreeNode left;
    5.       TreeNode right;
    6.       TreeNode() {}
    7.       TreeNode(int val) { this.val = val; }
    8.       TreeNode(int val, TreeNode left, TreeNode right) {
    9.           this.val = val;
    10.           this.left = left;
    11.           this.right = right;
    12.       }
    13.   }
    14.     LinkedList> res=new LinkedList<>();//记录最终结果：所有符合条件的路径
    15.     LinkedList path=new LinkedList<>();//遍历到的符合条件的某个路径
    16.     public List> pathSum(TreeNode root, int target) {
    17.         recur(root,target);
    18.         return res;
    19.     }
    20.  
    21.     private void recur(TreeNode root, int target) {
    22.         //1.递归终止条件：root==null
    23.         if(root==null){
    24.             return;
    25.         }
    26.         //2.将当前根节点的值加入路径，同时target减去根节点的值。
    27.         // 当根节点值归零同时左右子树为空，则当前节点就是叶子节点且满足所有值和等于target（因为target减完所有节点值自己值就归零，以此判断相等）
    28.           //此时该路径就是结点和为target的路径之一，将该路径加入结果集res中
    29.         path.add(root.val);
    30.         target=target-root.val;
    31.         if(target==0&&root.left==null&&root.right==null){
    32.             res.add(new LinkedList<>(path));
    33.         }
    34.         //3.遍历左右子树
    35.         recur(root.left,target);
    36.         recur(root.right,target);
    37.         //4.回溯计算是否有其他对应路径时应先将当前节点从路径path中删除
    38.         path.removeLast();
    39.     }
    40. }

    2.力扣_二叉搜索树与双向链表

            输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

    ​

    算法思路流程：
    1.递归法中序遍历-转为双向链表：

            终止条件：当节点cur为空，代表越过叶节点，直接返回；
            递归左子树，即 dfs(cur.left) ；
            构建链表：
            1）当 pre 为空时：代表正在访问链表头节点，记为 head ；
            2）当 pre 不为空时：修改双向节点引用，即pre.right=cur，cur.left=pre；
                    保存cur： 更新 pre = cur ，即节点 cur 是后继节点的 pre ；
            递归右子树，即 dfs(cur.right) ；
    2.treeToDoublyList(root)：

            特例处理：若节点root为空，则直接返回；
            初始化：空节点pre；
            转化为双向链表：调用 dfs(root) ；
            构建循环链表： 中序遍历完成后，head 指向头节点， pre 指向尾节点，因此修改 head 和 pre 的双向节点引用即可；
            返回值： 返回链表的头节点 head 即可；

    1.  Node pre;//前驱结点
    2.     Node head;//头节点
    3.     public Node treeToDoublyList(Node root) {
    4.         if(root==null){
    5.             return null;
    6.         }
    7.         //此时节点不为空，构建有序双向链表
    8.         dfs(root);
    9.         //此时得到了链表是有序双向链表，头节点是head,尾结点是prev（cur走到空时pre刚好走到尾部）
    10.         //头节点.pre是尾结点，尾结点.next是头节点即得到循环链表
    11.         head.left=pre;
    12.         pre.right=head;
    13.         return head;
    14.     }
    15.         //二叉树转为有序双向链表
    16.         //有序：通过中序遍历实现：中序遍历结果是一个排序好的顺序值
    17.         //这个方法的用途就是把二叉树转为有序双向链表
    18.     private void dfs(Node cur) {
    19.         //1.当前结点cur为空，已越过叶子节点,直接返回
    20.         if(cur==null){
    21.             return;
    22.         }
    23.         //2.遍历左子树
    24.         dfs(cur.left);
    25.         //3.处理节点
    26.         //判断前驱pre是否为null，为null说明cur是头节点
    27.         if(pre==null){
    28.             head=cur;
    29.         }else{
    30.            pre.right=cur;
    31.         }
    32.         cur.left=pre;
    33.         //更新pre的值为cur：即节点cur是后继节点的pre
    34.         pre=cur;
    35.         /**
    36.          * if(prev!=null){
    37.          *                         //prev的下一位是待处理的根节点，但不是头节点
    38.          *                         //连接
    39.          *                         prev.right=root;
    40.          *                         root.left=prev;
    41.          *                         //prev往后走一位
    42.          *                         prev=root;
    43.          *                 }else{
    44.          *                         //prev的下一位即root就是头节点
    45.          *                         head=root;
    46.          *                         prev=head;
    47.          *                 }
    48.          */
    49.         //4.遍历右子树
    50.         dfs(cur.right);
    51.     }

    另一种写法：

    1. class Solution {
    2.      Node tail;
    3.     public Node treeToDoublyList(Node root) {
    4.        if(root==null){
    5.            return null;
    6.        }
    7.        //treeToDoublyListHelper（）：求双向有序列表
    8.        Node head=treeToDoublyListHelper(root);
    9.        //连接首尾
    10.        head.left=tail;
    11.        tail.right=head;
    12.        return head;
    13.     }
    14.     public Node treeToDoublyListHelper(Node root) {
    15.         if(root==null){
    16.             return null;
    17.         }
    18.         //对二叉树进行中序遍历：保证顺序。
    19.         //递归函数进行的操作是二叉树变为双向链表
    20.         Node leftHead=treeToDoublyListHelper(root.left);
    21.         Node leftTail=leftHead;
    22.         //找左子树尾节点
    23.         while(leftTail!=null&&leftTail.right!=null){
    24.             leftTail=leftTail.right;
    25.         }
    26.         //此时leftTail是左子树尾节点
    27.         if(leftTail!=null){
    28.             leftTail.right=root;
    29.             root.left=leftTail;
    30.         }
    31.         //左子树连接完毕
    32.         //处理右边
    33.         Node rightHead=treeToDoublyListHelper(root.right);
    34.         if(rightHead!=null){
    35.             rightHead.left=root;
    36.             root.right=rightHead;
    37.         }
    38.         tail=rightHead;
    39.         while(tail!=null&&tail.right!=null){
    40.             tail=tail.right;//走完tail是尾节点
    41.         }
    42.         if(tail==null){
    43.             tail=root;
    44.         }
    45.         //返回大链表的根节点(头节点)：两种情况
    46.         //左树为空返回root，不为空返回左树头节点
    47.         return leftHead==null?root:leftHead;
    48.     }
    49. }

    3.力扣_二叉搜索树的第k大结点

    给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

    分析：

            1.二叉搜索树的中序遍历是一个递增序列，那么，中序遍历的倒叙就是递减序列。因此，求 “二叉搜索树第 kk 大的节点” 可转化为求 “此树的中序遍历倒序的第k个节点”。中序遍历：左根右，倒序：右左根。

            2.为求第k个节点，需要实现以下三项工作：
            1）递归遍历时计数，统计当前节点的序号；
            2）递归到第k个节点时，应记录结果res；
            3）记录结果后，后续的遍历即失去意义，应提前终止（即返回）。

            3.递归解析：
                    终止条件：当节点root为空（越过叶子节点），则直接返回；
                    递归右子树：即dfs(root.right) ；
                    三项工作：
                    a. 提前返回：若k=0，代表已找到目标节点，无需继续遍历，因此直接返回；
                    b.统计序号：执行k=k-1（即从k减至0）；
                    c.记录结果：若k=0，代表当前节点为第 kk 大的节点，因此记录 res = root.valres=root.val ；
                    递归左子树：即dfs(root.left) ；

    1. public class Num54_二叉树第k大结点 {
    2.     private class TreeNode {
    3.       int val;
    4.       TreeNode left;
    5.       TreeNode right;
    6.       TreeNode(int x) { val = x; }
    7.   }
    8.     int res;//结果
    9.     int k;//第k大结点
    10.     public int kthLargest(TreeNode root, int k) {
    11.         this.k=k;
    12.         //求二叉树第k大结点
    13.         dfs(root);
    14.         return res;
    15.     }
    16.     //中序遍历的倒叙：中序遍历得到一个升序值，她的倒叙就是一个降序，第k大就变为求第k个结点
    17.     //中序：左根右；倒序后：右根左
    18.     private void dfs(TreeNode root) {
    19.         if(root==null){
    20.             return;
    21.         }
    22.         dfs(root.right);
    23.         //处理结点
    24.         if(k==0){
    25.             return;
    26.         }
    27.         if(--k==0){//k不断减减到0时，得到的那个结点就是第k大结点，拿到节点值直接返回即可
    28.             res=root.val;
    29.         }
    30.         dfs(root.left);
    31.     }
    32. }

    4.二叉树的深度

    1. /**
    2.  * 输入一棵二叉树的根节点，求该树的深度。
    3.  * 从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
    4.  **/
    5.  
    6. /**
    7.  * 思路：二叉树的深度左右子树长度较长的那个的长度+根节点长度
    8.  */
    9. public class Num55_I二叉树的深度 {
    10.     public class TreeNode {
    11.       int val;
    12.       TreeNode left;
    13.       TreeNode right;
    14.       TreeNode(int x) { val = x; }
    15.   }
    16.     public int maxDepth(TreeNode root) {
    17.         if(root==null){
    18.             return 0;
    19.         }
    20.         //根节点存在，求左右子树深度
    21.         return Math.max(maxDepth(root.left),maxDepth(root.right))+1;//加1是加上当前节点的长度
    22.     }
    23. }

    5.力扣_平衡二叉树

            输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

    Math.abs(x-y)：计算两个数字之间的距离值

    1. /**
    2.  * 如何判断一个树root是否为平衡树：
    3.  * 以root为根节点的二叉树左右子树的高度差<=1并且左右子树分别也都是平衡树
    4.  */
    5. public class Num55_II平衡二叉树 {
    6.     public class TreeNode {
    7.       int val;
    8.       TreeNode left;
    9.       TreeNode right;
    10.       TreeNode(int x) { val = x; }
    11.   }
    12.     public boolean isBalanced(TreeNode root) {
    13.         if(root==null){
    14.             return true;
    15.         }
    16.         //求当前节点左右子树高度差
    17.         //当高度差<=1并且左右子树都是平衡二叉树即整个树是平衡二叉树
    18.         return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
    19.     }
    20.     //计算树的高度
    21.     private int height(TreeNode node) {
    22.         if(node==null){
    23.             return 0;
    24.         }
    25.         return 1+Math.max(height(node.left),height(node.right));
    26.     }
    27. }

    优化：记忆化搜索⭐

            在判断平衡树的过程中，若干个节点可能会被重复计算多次，造成了递归的重复执行，越靠下的节点，重复几率越高，可以使用记忆化搜索优化这种情况。

            记忆化搜索：在递归过程中，若某个节点的高度已经被计算过了，我们就使用Map存储该节点以及其高度值，下次再用到这个节点的时候，我们直接从Map中取高度即可，避免多次重复的递归过程

    1.     private Map nodeMap=new HashMap<>();//存储结点及其对应高度
    2.     public boolean isBalanced(TreeNode root) {
    3.         if(root==null){
    4.             return true;
    5.         }
    6.         int left=0;
    7.         int right=0;
    8.         if(nodeMap.containsKey(root.left)){
    9.             //此时左树高度已经被计算过了，直接从Map中取出节点值对应高度
    10.             left=nodeMap.get(root.left);
    11.         }else {
    12.             //否则，计算左子树高度，并将高度放入Map集合中
    13.             left=height(root.left);
    14.             nodeMap.put(root.left,left);
    15.         }
    16.         if(nodeMap.containsKey(root.right)){
    17.             right=nodeMap.get(root.right);
    18.         }else {
    19.             right=height(root.right);
    20.             nodeMap.put(root.right,right);
    21.         }
    22.         return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    23.     }
    24.  
    25.     private int height(TreeNode node) {
    26.         if(node==null){
    27.             return 0;
    28.         }
    29.         return 1+Math.max(height(node.left),height(node.right));
    30.     }

    6.力扣_二叉树的最近公共祖先（不是回溯问题解法）

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

    1. /**
    2.  * 用整型变量接收是否找到节点p,q
    3.  * 我们在找p或q的祖先时顺便找最近公共祖先
    4.  */
    5. public class Num68_I二叉树的最近公共祖先 {
    6.     private class TreeNode {
    7.       int val;
    8.       TreeNode left;
    9.       TreeNode right;
    10.       TreeNode(int x) { val = x; }
    11.   }
    12.     //定义一个全局变量用于返回最近公共祖先
    13.     private TreeNode resNode;
    14.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    15.       lowestCommonAncestorHelper(root,p,q);
    16.       return resNode;
    17.     }
    18.  
    19.   /**
    20.    * 以当前root为根节点的二叉树是否能找到p或q
    21.    * 该方法不是找公共祖先的方法，只是判断当前树是否是p或q的祖先，找到一个就说明至少是一个结点的祖先
    22.    * 只是找是否是p或q的祖先的过程中判断了是否是公共祖先
    23.    */
    24.   private Boolean lowestCommonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) {
    25.     if(root==null){
    26.       return false;
    27.     }
    28.     //判断左右子树是否有包含p或q，根节点是否是p或q
    29.     int left=lowestCommonAncestorHelper(root.left,p,q)?1:0;
    30.     int right=lowestCommonAncestorHelper(root.right,p,q)?1:0;
    31.     int mid=(root==p||root==q)?1:0;
    32.     if(left+right+mid==2){
    33.       resNode=root;//相加和为2，根节点就是最近公共祖先
    34.     }
    35.     //否则，有没有祖先就是看就是看上面有没有大于零的数
    36.     return left+right+mid>0;
    37.   }
    38. }

  • 相关阅读:
    ADEP-12A-01-D2-2-3-52 ADEP-12A-01-D2-3-2-52控制闭环压力反馈比例放大器
    vagrant设置磁盘大小
    Java8使用stream分组和排序的实现
    【无标题】
    【jvm】虚拟机之本地方法栈
    应广单片机实现跑马灯
    [ Linux ] Linux调试器--gdb使用
    BERT 相关资源整理
    datax从ES读写数据
    K线形态识别_身怀六甲和十字胎
  • 原文地址：https://blog.csdn.net/m0_58006481/article/details/126072402