LeetCode题解——树（四）

电玩女神 2023-02-17 03:53 44阅读 0赞

### 文章目录 ###

*  BST
 *   *  将有序数组转换为二叉搜索树
     *   *  递归
     *  有序链表转换二叉搜索树
     *   *  递归
         *  中序遍历
     *  两数之和 IV - 输入 BST
     *   *  中序遍历
     *  二叉搜索树的最小绝对差
     *   *  中序遍历
         *  中序遍历优化
     *  二叉搜索树中的众数
     *   *  中序遍历
         *  Morris中序遍历
 *  字典树
 *   *  实现 Trie (前缀树)
     *   *  解法
     *  键值映射
     *   *  解法
         *   *  推荐阅读

# BST #

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
    
    给定有序数组: [-10,-3,0,5,9],
    
    一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            return toBeBST(nums, 0, nums.length - 1);
        }
        private TreeNode toBeBST(int[] nums, int left, int right) {
        
            if (left > right) {
        
                return null;
            }
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = toBeBST(nums, left, mid - 1);
            root.right = toBeBST(nums, mid + 1, right);
            return root;
        }
    
    }

## 有序链表转换二叉搜索树 ##

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
    
    给定的有序链表： [-10, -3, 0, 5, 9],
    
    一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

### 递归 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode sortedListToBST(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            if (head.next == null) {
        
                return new TreeNode(head.val);
            }
            ListNode preMid = preMid(head);
            ListNode mid = preMid.next;
            preMid.next = null;
            TreeNode root = new TreeNode(mid.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(mid.next);
            return root;
        }
        private ListNode preMid(ListNode head) {
        
            ListNode slow = head, fast = head.next;
            ListNode pre = head;
            while(fast != null && fast.next != null) {
        
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            return pre;
        }
    }

### 中序遍历 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private ListNode head;
        private int findSize(ListNode node) {
        
            ListNode ptr = node;
            int count = 0;
            while (ptr != null) {
        
                ptr = ptr.next;
                count++;
            }
            return count;
        }
        private TreeNode toBeBST(int left, int right) {
        
            if (left > right) {
        
                return null;
            }
            int mid = (left + right) / 2;
            TreeNode leftNode = toBeBST(left, mid - 1);
            TreeNode node = new TreeNode(this.head.val);
            node.left = leftNode;
            this.head = this.head.next;
            node.right = toBeBST(mid + 1, right);
            return node;
        }
        public TreeNode sortedListToBST(ListNode head) {
        
            if (head == null) {
        
                return null;
            }
            if (head.next == null) {
        
                return new TreeNode(head.val);
            }
            int size = findSize(head);
            this.head = head;
            return toBeBST(0, size - 1);
        }
    }

## 两数之和 IV - 输入 BST ##

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:
    
    输入: 
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Target = 9
    
    输出: True
     
    
    案例 2:
    
    输入: 
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Target = 28
    
    输出: False

### 中序遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean findTarget(TreeNode root, int k) {
        
            List<Integer> nums = new ArrayList<>();
            inOrder(root, nums);
            int i = 0, j = nums.size() - 1;
            while(i < j) {
        
                int sum = nums.get(i) + nums.get(j);
                if (sum == k) {
        
                    return true;
                } else if (sum < k) {
        
                    i++;
                } else {
        
                    j--;
                }
            }
            return false;
        }
        private void inOrder(TreeNode node, List<Integer> nums) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left, nums);
            nums.add(node.val);
            inOrder(node.right, nums);
        }
    }

## 二叉搜索树的最小绝对差 ##

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：
    
    输入：
    
       1
        \
         3
        /
       2
    
    输出：
    1
    
    解释：
    最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     
    
    提示：
    
    树中至少有 2 个节点。
    本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

### 中序遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int getMinimumDifference(TreeNode root) {
        
            List<Integer> nums = new ArrayList<>();
            int min = Integer.MAX_VALUE;
            inOrder(root, nums);
            int size = nums.size();
            int j = 1;
            for (int i = 0; i < size - 1 && j <= size - 1; ) {
        
                int tmp = Math.abs(nums.get(i) - nums.get(j));
                if (tmp < min) {
        
                    min = tmp;
                }
                i++;
                j++;
            }
            return min;
        }
        private void inOrder(TreeNode node, List<Integer> nums) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left, nums);
            nums.add(node.val);
            inOrder(node.right, nums);
        }
    }

### 中序遍历优化 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private TreeNode preNode = null;
        private int min = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
        
            inOrder(root);
            return min;
        }
        private void inOrder(TreeNode node) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left);
            if (preNode != null) {
        
                min = Math.min(min, Math.abs(preNode.val - node.val));
            }
            preNode = node;
            inOrder(node.right);
        }
    }

## 二叉搜索树中的众数 ##

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：
    
    结点左子树中所含结点的值小于等于当前结点的值
    结点右子树中所含结点的值大于等于当前结点的值
    左子树和右子树都是二叉搜索树
    例如：
    给定 BST [1,null,2,2],
    
       1
        \
         2
        /
       2
    返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

### 中序遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private TreeNode preNode = null;
        private int curCount = 1;
        private int maxCount = 1;
        public int[] findMode(TreeNode root) {
        
            List<Integer> nums = new ArrayList<>();
            inOrder(root, nums);
            int i = 0;
            int[] res = new int[nums.size()];
            for (int num : nums) {
        
                res[i++] = num;
            }
            return res;
        }
        private void inOrder(TreeNode node, List<Integer> nums) {
        
            if (node == null) {
        
                return;
            }
            inOrder(node.left, nums);
            if (preNode != null) {
        
                if (preNode.val == node.val) {
        
                    curCount++;
                } else {
        
                    curCount = 1;
                }
            }
            if (curCount > maxCount) {
        
                maxCount = curCount;
                nums.clear();
                nums.add(node.val);
            } else if (curCount == maxCount) {
        
                nums.add(node.val);
            }
            preNode = node;
            inOrder(node.right, nums);
        }
    }

### Morris中序遍历 ###

详解见[https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/lian-di-gui-du-bu-yong-de-chang-shu-kong-jian-fu-z/][https_leetcode-cn.com_problems_find-mode-in-binary-search-tree_solution_lian-di-gui-du-bu-yong-de-chang-shu-kong-jian-fu-z]

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int[] findMode(TreeNode root) {
        
            TreeNode cur = root, pre = null;
            ArrayList<Integer> nums = new ArrayList<>();
            int curCount = 1, maxCount = 1;
            while (cur != null) {
        
                if (cur.left == null) {
         // 左子树为空，直接比较
                    if (pre != null && pre.val == cur.val) {
        
                        curCount++;
                    } else {
        
                        curCount = 1;
                    }
                    if (curCount > maxCount) {
        
                        maxCount = curCount;
                        nums.clear();
                        nums.add(cur.val); 
                    } else if (curCount == maxCount) {
        
                        nums.add(cur.val); 
                    }
                    pre = cur;
                    cur = cur.right;
                } else {
         // 进入左子树
                    TreeNode preTemp = cur.left;
                    while (preTemp.right != null && preTemp.right != cur) {
        
                        preTemp = preTemp.right;
                    }
                    if (preTemp.right == cur) {
        
                        if (pre != null && pre.val == cur.val) {
        
                            curCount++;
                        } else {
        
                            curCount = 1;
                        }
                        if (curCount > maxCount) {
        
                            maxCount = curCount;
                            nums.clear();
                            nums.add(cur.val); 
                        } else if (curCount == maxCount) {
        
                            nums.add(cur.val);
                        }
                        preTemp.right = null;
                        pre = cur;
                        cur = cur.right;
                    } else {
        
                        preTemp.right = cur;
                        cur = cur.left;
                    }
                }
            }
            int[] res = new int[nums.size()];
            int index = 0;
            for (int num : nums) {
        
                res[index++] = num;
            }
            return res;
        }
    }

# 字典树 #

## 实现 Trie (前缀树) ##

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:
    
    Trie trie = new Trie();
    
    trie.insert("apple");
    trie.search("apple");   // 返回 true
    trie.search("app");     // 返回 false
    trie.startsWith("app"); // 返回 true
    trie.insert("app");   
    trie.search("app");     // 返回 true
    说明:
    
    你可以假设所有的输入都是由小写字母 a-z 构成的。
    保证所有输入均为非空字符串。

### 解法 ###

class Trie {
        
    
        /** Initialize your data structure here. */
        public Trie() {
        
            
        }
        
        private class Node {
        
            Node[] children = new Node[26];
            boolean isLeaf;
        }
        
        private Node root = new Node();
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
        
            insert(word, root);
        }
        
        private void insert(String word, Node node) {
        
            if (node == null) {
        
                return;
            }
            if (word.length() == 0) {
        
                node.isLeaf = true;
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.children[index] == null) {
        
                node.children[index] = new Node();
            }
            insert(word.substring(1), node.children[index]);
        }
        
        private int indexForChar(char c) {
        
            return c - 'a';
        }
            
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
        
            return search(word, root);
        }
        
        private boolean search(String word, Node node) {
        
            if (node == null) {
        
                return false;
            }
            if (word.length() == 0) {
        
                return node.isLeaf;
            }
            int index = indexForChar(word.charAt(0));
            return search(word.substring(1), node.children[index]);
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
        
            return startsWith(prefix, root);
        }
        
        private boolean startsWith(String prefix, Node node) {
        
            if (node == null) {
        
                return false;
            }
            if (prefix.length() == 0) {
        
                return true;
            }
            int index = indexForChar(prefix.charAt(0));
            return startsWith(prefix.substring(1), node.children[index]);
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */

## 键值映射 ##

实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:
    
    输入: insert("apple", 3), 输出: Null
    输入: sum("ap"), 输出: 3
    输入: insert("app", 2), 输出: Null
    输入: sum("ap"), 输出: 5

### 解法 ###

class MapSum {
        
        
        private class Node {
        
            Node[] children = new Node[26];
            int value;
        }
        
        private Node root = new Node();
    
        /** Initialize your data structure here. */
        public MapSum() {
        
        
        }
        
        public void insert(String key, int val) {
        
            insert(key, root, val);
        }
        
        private void insert(String key, Node node, int val) {
        
            if (key == null) {
        
                return;
            }
            if (key.length() == 0) {
        
                node.value = val;
                return;
            }
            int index = indexForChar(key.charAt(0));
            if (node.children[index] == null) {
        
                node.children[index] = new Node();
            }
            insert(key.substring(1), node.children[index], val);
        }
        
        private int indexForChar(char c) {
        
            return c - 'a';
        }
        
        public int sum(String prefix) {
        
            return sum(prefix, root);
        }
        
        private int sum(String prefix, Node node) {
        
            if (node == null) {
        
                return 0;
            }
            if (prefix.length() != 0) {
        
                int index = indexForChar(prefix.charAt(0));
                return sum(prefix.substring(1), node.children[index]);
            }
            int sum = node.value;
            for (Node child : node.children) {
        
                sum += sum(prefix, child);
            }
            return sum;
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[https_leetcode-cn.com_problems_find-mode-in-binary-search-tree_solution_lian-di-gui-du-bu-yong-de-chang-shu-kong-jian-fu-z]: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/lian-di-gui-du-bu-yong-de-chang-shu-kong-jian-fu-z/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png