Day15_树的遍历_剑指Offer

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

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

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

示例：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
输入：root = [1,2,3], targetSum = 5
输出：[]
输入：root = [1,2], targetSum = 0
输出：[]

限制：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解题思路

明确题目要求，叶子节点到根节点的路径和为target

写入结果判断需要满足：是叶子节点（now.left == null && now.right == null）路径和为target

对于树结构，从根目录出发到叶子节点显然比反过来方便，值转递上也使用 target - now.val

实现：

定义全局变量：ans 记录最后结论，midList记录每一条结论
先不断递归 target - now.val 直到叶子节点，途中的值写入中间变量midList
判断是否满足上述写入判断（now.left == null && now.right == null && target == 0）。如果是，写入当前midList至ans
回到上一级，判断是否可以走另外的子节点，回到2判断
遍历完成，返回全局变量ans

Java代码

/**
 * 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 {
    LinkedList<List<Integer>> ans = new LinkedList<List<Integer>>();;
    LinkedList<Integer> midList = new LinkedList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        findWay(root, target);
        return ans;
    }

    public void findWay(TreeNode root, int target) {
        if(root == null) return;
        midList.add(root.val); 
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) {
            ans.add(new LinkedList(midList));
        }
        findWay(root.left, target);
        findWay(root.right, target);
        midList.removeLast();
        return;
    }
}

二叉搜索树与双向链表

medium 原题连接：二叉搜索树与双向链表

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

我们希望将二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个

节点的后继是第一个节点。

解题思路

对于二叉搜索树，树中每个节点都满足：一个节点的左子树值小于根节点值，右子树值大于根节点值

而对于中序遍历：先遍历左子树，再读取当前节点，最后读取右子树

综合以上两者，我们会发现，中序遍历的二叉搜索树就是一个排好序的输出

实现：

对于原根节点，进行中序遍历
依次遍历左节点，直至叶子节点
当前是未记录的最小值，左节点连以记录最大值，当前就是已记录的尾节点；如果当前没记录，就设未头节点（最小值）
遍历右节点，回到 2，直至完成遍历
连接头节点和尾节点

Java代码

/*
// 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 {
    Node pre, head;
    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) head = cur;
        else pre.right = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

二叉搜索树的第k大节点

Esay 原题连接：二叉搜索树的第k大节点

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

示例：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

提示：

1 ≤ k ≤ 二叉搜索树元素个数

解题思路

二叉搜索树：左子树值 < 根节点值 < 右子树值

以右，中，左的顺序遍历每一个子节点，减少方法的传参量，将第k大的要求k设定为全局参数

每递归到一位就对应减 1 ，直至到达第 k 大的数据时返回

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) ans = root.val;
        dfs(root.left);
    }
}