阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等

目录

搜索与回溯算法 

1 二叉树中和为某一值的路径

1. DFS

​2. 优化

 2 二叉搜索树与双向链表

1. 中序遍历 

2. DFS

3 二叉搜索树的第k大节点 

1. 递归+中序遍历

2. 递归+中序遍历倒序


搜索与回溯算法 

1 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

1. DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        Deque<Integer> t = new LinkedList<>();
        dfs(root, target, 0,t);
        return res;
    }
    public int dfs(TreeNode root, int target,int sum,Deque<Integer> t){
        if(root == null) return 0;
        t.offer(root.val);
        sum+=root.val;
//        System.out.println("t: "+t);
        if(root.right == null && root.left == null) {
//            System.out.println("sum "+sum);
            if(sum == target){
                res.add(new LinkedList<>(t));
            } 
        }
        if(0 != dfs(root.left, target,sum,t))
            t.removeLast();
        if(0 != dfs(root.right, target,sum,t))
            t.removeLast();
        return 1;
    }
}

阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等2. 优化

package jzof.Day15;

import jzof.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ahan
 * @create_time 2021-11-15-7:21 下午
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 */
public class _34 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(5);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(8);
        TreeNode node3 = new TreeNode(11);
        TreeNode node4 = new TreeNode(13);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(7);
        TreeNode node7 = new TreeNode(2);
        TreeNode node8 = new TreeNode(5);
        TreeNode node9 = new TreeNode(1);
        head.left = node1;
        head.right = node2;
        node1.left = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;

        List<List<Integer>> lists = new _34().pathSum(head, 22);
        System.out.println(lists);
    } 
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        Deque<Integer> temp = new LinkedList<>();
        dfs(root, target,temp);
        return res;
    }
    void dfs(TreeNode cur, int sum, Deque<Integer> temp){
        if(cur == null) return ;
        temp.add(cur.val);
        sum -= cur.val;
        System.out.println(temp);
        if(cur.left == null && cur.right == null && 0 == sum)
            res.add(new LinkedList<>(temp));
        dfs(cur.left, sum,temp);
        dfs(cur.right, sum,temp);
        temp.removeLast();
    }
}

 2 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

想到了用中序遍历,还是写的很粗糙,没有用dfs实现,发现使用类变量保存递归过程的上一次递归中结果很有用!

1. 中序遍历 

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if(root==null)
            return null;

        Deque<Node> stack = new LinkedList<>();
        Deque<Node> res = new LinkedList<>();

        Node head ;
        Node curNode = root;
        Node preNode ;
        while(curNode!=null || !stack.isEmpty()){
            while(curNode!=null){
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            res.offer(curNode);
            // System.out.println("curNode: "+curNode+" val: "+curNode.val+" left: "+curNode.left+" right: "+curNode.right);
            curNode = curNode.right;
        }
        // System.out.println(res);
        preNode = res.poll();
        head = preNode;
        curNode = head;
        while (!res.isEmpty()){
            curNode = res.poll();
            preNode.right = curNode;
            curNode.left = preNode;
            preNode = curNode;
        }
        // System.out.println(curNode);
        head.left = curNode;
        curNode.right = head;
        return head;
    }
}

阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等

2. DFS

 解题思路:

二叉搜索树的中序遍历为 递增序列 ,所以转换成一个 “排序的循环双向链表” ,其中包含三个要素:

  1. 排序链表: 节点应从小到大排序,因此应使用 中序遍历 “从小到大”访问树的节点。
  2. 双向链表: 在构建相邻节点的引用关系时,设前驱节点 pre 和当前节点 cur ,不仅应构建 pre.right = cur ,也应构建 cur.left = pre 。
  3. 循环链表: 设链表头节点 head 和尾节点 tail ,则应构建 head.left = tail 和 tail.right = head 。

算法流程:

dfs(cur): 递归法中序遍历;

  1. 终止条件: 当节点 cur 为空,代表越过叶节点,直接返回;
  2. 递归左子树,即 dfs(cur.left) ;
  3. 构建链表:
    1. 当 pre 为空时: 代表正在访问链表头节点,记为 head ;
    2. 当 pre 不为空时: 修改双向节点引用,即 pre.right=cur ,cur.left = pre ;
    3. 保存 cur : 更新 pre = cur ,即节点 cur 是后继节点的 pre ;
  4. 递归右子树,即 dfs(cur.right) ;
  5. 特例处理: 若节点 root 为空,则直接返回;
  6. 初始化: 空节点 pre ;
  7. 转化为双向链表: 调用 dfs(root) ;
  8. 构建循环链表: 中序遍历完成后,head 指向头节点, pre 指向尾节点,因此修改 head 和 pre 的双向节点引用即可;
  9. 返回值: 返回链表的头节点 head 即可;
class Solution {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur){
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等

3 二叉搜索树的第k大节点 

剑指 Offer 34. 二叉树中和为某一值的路径阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/解题思路:

本文解法基于此性质:二叉搜索树的中序遍历为 递增序列 。

因此, “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。

 递归解析:

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

1. 递归+中序遍历

跑完全部节点再查找中序遍历的第size()-k个节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        Deque<Integer> res = new LinkedList<>();
        TreeNode curNode = root;
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode =  stack.pop();
            res.offer(curNode.val);
            curNode = curNode.right;
        } 
        return (int) res.stream().sorted().toArray()[res.size() - k];
    }
}

阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等

public class Solution {

    private static List<Integer> arr=new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        //中序遍历,正序赋值数组
        inOrder(root);
        //寻找第k大的数,输出
        return arr.get(arr.size()-k);
    }
    //中序遍历
    private static void inOrder(TreeNode root){
        if(root==null)
            return;
        inOrder(root.left);
        arr.add(root.val);
        inOrder(root.right);

    }
}

2. 递归+中序遍历倒序

class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
} 

利用类变量维护数值,挺好~

阿翰 剑指offer 之 Day 15 搜索与回溯算法 4 中等

复杂度分析:

  • 时间复杂度 O(N): 当树退化为链表时(全部为右子节点),无论 k 的值大小,递归深度都为 N ,占用 O(N) 时间。
  • 空间复杂度 O(N): 当树退化为链表时(全部为右子节点),系统使用 O(N) 大小的栈空间。

 

上一篇:沟通无限校园网--最小生成树(prim算法)


下一篇:Leetcode103. 二叉树的锯齿形层序遍历