【LeetCode】《剑指Offer》第Ⅳ篇⊰⊰⊰ 32 - 38题

àì夳堔傛蜴生んèń 2022-11-04 00:49 3阅读 0赞

## 【LeetCode】《剑指Offer》第Ⅳ篇⊰⊰⊰ 32 - 38题 ##

### 文章目录 ###

*   *  【LeetCode】《剑指Offer》第Ⅳ篇⊰⊰⊰ 32 - 38题
     *   *  32-Ⅰ. 从上到下打印二叉树（medium）
         *  32-Ⅱ. 从上到下打印二叉树 II（easy）
         *  32-Ⅲ. 从上到下打印二叉树 III（medium）
         *  33. 二叉搜索树的后序遍历序列（medium）
         *  34. 二叉树中和为某一值的路径（medium）
         *  35. 复杂链表的复制（medium）
         *  36. 二叉搜索树与双向链表（medium）
         *  37. 序列化二叉树（hard）
         *  38. 字符串的排列（medium）

### 32-Ⅰ. 从上到下打印二叉树（medium） ###

[剑指 Offer 32 - I. 从上到下打印二叉树][Offer 32 - I.]

【**题目**】从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

【**示例**】

给定二叉树: `[3,9,20,null,null,15,7]`,

返回`[3,9,20,15,7]`

【**解题思路**】

层次遍历

class Solution {
        
        public int[] levelOrder(TreeNode root) {
        
            if (root == null) return new int[]{
        };
           
            List<Integer> list = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root); 
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
    
            int []res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
            return res;
        }
    }

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

### 32-Ⅱ. 从上到下打印二叉树 II（easy） ###

[剑指 Offer 32 - II. 从上到下打印二叉树 II][Offer 32 - II. _ II]

【**题目**】从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

【**示例**】

给定二叉树: [3,9,20,null,null,15,7],
        3
       / \
      9  20
        /  \
       15   7
    返回其层次遍历结果：
    [
      [3],
      [9,20],
      [15,7]
    ]

【**解题思路**】

层次遍历

class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            if (root == null) {
        
                return new ArrayList<>();
            }
            List<List<Integer>> list = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                List<Integer> l = new ArrayList<>();
                int len = queue.size();
                while (len > 0) {
        
                    TreeNode p = queue.poll();
                    l.add(p.val);
                    if (p.left != null) {
        
                        queue.offer(p.left);
                    }
                    if (p.right != null) {
        
                        queue.offer(p.right);
                    }
                    len--;
                }
                list.add(l);
            }
            return list;
        }
    }

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

### 32-Ⅲ. 从上到下打印二叉树 III（medium） ###

[剑指 Offer 32 - III. 从上到下打印二叉树 III][Offer 32 - III. _ III]

【**题目**】请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

【**解题思路**】

递归或者层次遍历

class Solution {
        
        List<List<Integer>> list;
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            list = new ArrayList();
            iter(root, 0);
            return list;
        }
    
        public void iter(TreeNode root, int deep){
        
            if (root == null) return;
            if (list.size() == deep) list.add(new ArrayList<>());
            if (deep % 2 == 0) {
        
                list.get(deep).add(root.val);
            } else {
        
                list.get(deep).add(0, root.val);
            }
            iter(root.left, deep + 1);
            iter(root.right, deep + 1);
        }
    }

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

### 33. 二叉搜索树的后序遍历序列（medium） ###

[剑指 Offer 33. 二叉搜索树的后序遍历序列][Offer 33.]

【**题目**】输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 `true`，否则返回 `false`。假设输入的数组的任意两个数字都互不相同。

**提示：**`数组长度 <= 1000`

【**示例**】

5
        / \
       2   6
      / \
     1   3
    输入: [1,6,3,2,5]
    输出: false
    -------------------
    输入: [1,3,2,6,5]
    输出: true

【**解题思路**】

单调栈

class Solution {
        
        public boolean verifyPostorder(int[] postorder) {
        
            Stack<Integer> stack = new Stack<>();
            int parent = Integer.MAX_VALUE;
            //逆向遍历，就是翻转的先序遍历
            for (int i = postorder.length - 1; i >= 0; i--) {
        
                int cur = postorder[i];
                while (!stack.isEmpty() && cur < stack.peek()) {
        
                    parent = stack.pop();
                }
                if (cur > parent) {
        
                    return false;
                }
                stack.add(cur);
            }
            return true;
        }
    }

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

### 34. 二叉树中和为某一值的路径（medium） ###

[剑指 Offer 34. 二叉树中和为某一值的路径][Offer 34.]

【**题目**】输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

【**示例**】

给定如下二叉树，以及目标和 sum = 22
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    返回：
    [
       [5,4,11,2],
       [5,8,4,5]
    ]

【**解题思路**】

递归

class Solution {
        
        List<List<Integer>> res;
        List<Integer> list;
        
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            res = new ArrayList();
            list = new ArrayList<Integer>();
            iter(root, sum);
            return res;
        }
    
        private void iter(TreeNode root, int sum) {
        
            if (root == null) return;
            sum -= root.val;
            list.add(root.val);
            if (root.left == null && root.right == null && sum == 0) {
        
                res.add(new ArrayList<Integer>(list));
            }
            iter(root.left, sum);
            iter(root.right, sum);
            list.remove(list.size() - 1);
        }
    }

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

### 35. 复杂链表的复制（medium） ###

[剑指 Offer 35. 复杂链表的复制][Offer 35.]

【**题目**】请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 `next` 指针指向下一个节点，还有一个 `random` 指针指向链表中的任意节点或者 `null`。

**提示：**

*  `-10000 <= Node.val <= 10000`
 *  `Node.random` 为空（null）或指向链表中的节点。
 *  节点数目不超过 1000 。

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

【**解题思路**】

方法一：HashMap

/*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    class Solution {
        
        public Node copyRandomList(Node head) {
        
            Map<Node, Node> map = new HashMap<>();
            for (Node p = head; p != null; p = p.next) {
        
                map.put(p, new Node(p.val));
            }
            for (Node p = head; p != null; p = p.next) {
        
                map.get(p).next = map.get(p.next);
                map.get(p).random = map.get(p.random);
            }
            return map.get(head);
        }
    }

方法二：原地算法

class Solution {
        
        public Node copyRandomList(Node head) {
        
            if (head == null) return head;
            Node cur = head;
            //复制
            while (cur != null) {
        
                Node p = new Node(cur.val);
                p.next = cur.next;
                cur.next = p;
                cur = p.next;
            }
            //连接
            cur = head;
            while (cur != null) {
        
                Node p = cur.next;
                if (cur.random != null) {
        
                    p.random = cur.random.next;
                }
                cur = cur.next.next;
            }
            //拆分
            Node res = head.next, t = res;
            cur = head;
            while (cur != null) {
        
                cur.next = cur.next.next;
                cur = cur.next;
                if (cur != null) {
        
                    t.next = cur.next;
                    t = t.next;
                }
            }
            return res;
        }
    }

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

### 36. 二叉搜索树与双向链表（medium） ###

[剑指 Offer 36. 二叉搜索树与双向链表][Offer 36.]

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

为了让您更好地理解问题，以下面的二叉搜索树为例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

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

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

【**解题思路**】

中序遍历

class Solution {
        
        Node head, pre;
        public Node treeToDoublyList(Node root) {
        
            if (root == null) return null;
            helper(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
    
        private void helper(Node cur) {
        
            if (cur == null) return;
            helper(cur.left);
            if (head == null) head = cur;
            if (pre == null) {
        
                pre = cur;
            } else {
        
                cur.left = pre;
                pre.right = cur;
                pre = cur;
            }
            helper(cur.right);
        }
    }

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

### 37. 序列化二叉树（hard） ###

[剑指 Offer 37. 序列化二叉树][Offer 37.]

【**题目**】请实现两个函数，分别用来序列化和反序列化二叉树。

【**示例**】

你可以将以下二叉树：
    
        1
       / \
      2   3
         / \
        4   5
    
    序列化为 "[1,2,3,null,null,4,5]"

【**解题思路**】

层序遍历,

例如上面那棵树，序列化后为`"1,2,n,n,3,4,5,n,n,n,n"`

public class Codec {
        
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
        
            if (root == null) {
        
                return "";
            }
            StringBuffer sb = new StringBuffer("");
            ArrayDeque<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            sb.append(root.val);
            
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                sb.append(',');
                if (node.left == null) {
        
                    sb.append('n');
                } else {
        
                    queue.offer(node.left);
                    sb.append(node.left.val);
                }
                sb.append(',');
                if (node.right == null) {
        
                    sb.append('n');
                } else {
        
                    queue.offer(node.right);
                    sb.append(node.right.val);
                }
            }
            return sb.toString();
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        
            if (data.equals("")) {
        
                return null;
            }
            String[] spot = data.split(",");
            ArrayDeque<TreeNode> queue = new ArrayDeque();
            TreeNode root = new TreeNode(Integer.valueOf(spot[0]));
            queue.offer(root);
            int k = 1;
            
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                if (!spot[k].equals("n")) {
        
                    TreeNode lnode = new TreeNode(Integer.valueOf(spot[k]));
                    node.left = lnode;
                    queue.offer(lnode);
                } else {
        
                    node.left = null;
                }
                k++;
                if (!spot[k].equals("n")) {
        
                    TreeNode rnode = new TreeNode(Integer.valueOf(spot[k]));
                    node.right = rnode;
                    queue.offer(rnode);
                } else {
        
                    node.right = null;
                }
                k++;
            }
            return root;       
        }
    }

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

### 38. 字符串的排列（medium） ###

[剑指 Offer 38. 字符串的排列][Offer 38.]

【**题目**】输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

**限制：**

`1 <= s 的长度 <= 8`

【**示例**】

输入：s = "abc"
    输出：["abc","acb","bac","bca","cab","cba"]

【**解题思路**】

回溯法

关于求全排列的方法可以参考往期总结[【LeetCode】﹝回溯法ி﹞ 全排列、子集、组合问题][LeetCode_]

class Solution {
        
        List<String> list;
        public String[] permutation(String s) {
        
            list = new ArrayList<>();
            backtrack(s.toCharArray(), 0);
            String[] res = new String[list.size()];
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        }
    
        private void backtrack(char[] chars, int begin) {
        
            if (begin == chars.length - 1) {
        
                list.add(new String(chars));
                return;
            }
            Set<Character> set = new HashSet<>();
            for (int i = begin; i < chars.length; i++) {
        
                if (set.contains(chars[i])) continue;
                set.add(chars[i]);
                swap(chars, begin, i);
                backtrack(chars, begin + 1);
                swap(chars, begin, i);
            }
        }
    
        private void swap(char[] chars, int i, int j) {
        
            char c = chars[i];
            chars[i] = chars[j];
            chars[j] = c;
        }
    }

[Offer 32 - I.]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
[Offer 32 - II. _ II]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
[Offer 32 - III. _ III]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[Offer 33.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
[Offer 34.]: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[Offer 35.]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/a6c19c168ea84aa8aceddc67fec2ff0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/b1d0ab36ff6d4c88bea2d9b5efc30d14.png
[Offer 36.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/73c59847cbb840c9976e5a80e8bf2cf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221023/0f04dce6fd194783abc1c8122890055a.png
[Offer 37.]: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
[Offer 38.]: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
[LeetCode_]: https://blog.csdn.net/weixin_44368437/article/details/110859817