剑指offer：33-37记录

Myth丶恋晨 2023-07-13 03:27 1阅读 0赞

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

参考以下这颗二叉搜索树：

5  
/ \\  
2 6  
/ \\  
1 3  
示例 1：

输入: \[1,6,3,2,5\]  
输出: false  
示例 2：

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

提示：

数组长度 <= 1000

思路：找到第一个比根大的数字x，x右边所有数字都要比根大才符合定义。

然后对左右子树重复上述过程。

class Solution {
        int[] postorder;
        public boolean verifyPostorder(int[] postorder) {
            this.postorder=postorder;
            return verify(0, postorder.length - 1); 
        }
    
        // 递归实现
        private boolean verify(int left, int right){
            if (left >= right) return true;
            int rootValue = postorder[right]; // 当前根
    
            // 找出第一个大于根节点的，右边必须都在右子树中
            int k = left;
            while (k < right && postorder[k] < rootValue){ 
                k++;
            }
            //判断
            for (int i = k; i < right; i++){
                if (postorder[i] < rootValue) return false;
            }
            return verify(left, k - 1) && verify(k, right - 1);
        }
    }

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

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

示例:  
给定如下二叉树，以及目标和 sum = 22，

5  
/ \\  
4 8  
/ / \\  
11 13 4  
/ \\ / \\  
7 2 5 1  
返回:

\[  
\[5,4,11,2\],  
\[5,8,4,5\]  
\]

提示：

节点总数 <= 10000

思路：深搜+回溯

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        List<List<Integer>> ans=new ArrayList();
        List<Integer> temp=new ArrayList();
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            help(root,sum);
            return ans;
        }
        public void help(TreeNode root, int sum){
            if(root==null)return;
            temp.add(root.val);
            sum-=root.val;
            if(sum==0 && root.left==null && root.right==null){
                ans.add(new ArrayList(temp));
            }
           
            help(root.left,sum);
            help(root.right,sum);
            temp.remove(temp.size() - 1);
        }
    }

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

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

示例 1：

![20200310113307754.png][]

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

![20200310113327630.png][]

输入：head = \[\[1,1\],\[2,1\]\]  
输出：\[\[1,1\],\[2,1\]\]  
示例 3：

![20200310113337937.png][]

输入：head = \[\[3,null\],\[3,0\],\[3,null\]\]  
输出：\[\[3,null\],\[3,0\],\[3,null\]\]  
示例 4：

输入：head = \[\]  
输出：\[\]  
解释：给定的链表为空（空指针），因此返回 null。

提示：

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

思路：先把每个节点后面复制一个相同的节点，为了方便处理好random。然后再分开即可。

空间O(1)

/*
    // 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) {
            if (head == null) {
                return head;
            }
            //将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2'->3->3'
            for (Node node = head, copy = null; node != null; node = node.next.next) {
                copy = new Node(node.val);
                copy.next = node.next;
                node.next = copy;
            }
            //把拷贝节点的random指针安排上
            for (Node node = head; node != null; node = node.next.next) {
                if (node.random != null) {
                    node.next.random = node.random.next;
                }
            }
            //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
            Node newHead = head.next;
            for (Node node = head, temp = null; node != null && node.next != null;) {
                temp = node.next;
                node.next = temp.next;
                node = temp;
            }
    
            return newHead;
        }
    }

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

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

1  
/ \\  
2 3  
/ \\  
4 5

序列化为 "\[1,2,3,null,null,4,5\]"  
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

思路：我们普通的遍历（前序中序后序）序列，通常是不能唯一确定一个二叉树的，需要前中结合或者后中结合。是因为我们不知道哪里可以停止，比如例子中：到3时，我们不知道该挂到2的下面还是2两边都是null（3应该挂1的右边）。解决方法就是把所有的null记录下来，比如例子中的二叉树：前序：1，2，null，null，3，4，null，null，5，null，null。下面是在这种做法的实现。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
    
        public String serialize(TreeNode root) {      //用StringBuilder
            return ser_help(root, new StringBuilder()).toString();
        }
        
        public StringBuilder ser_help(TreeNode root, StringBuilder str){
            if(null == root){
                str.append("null,");
                return str;
            }
            str.append(root.val); 
            str.append(",");
            str = ser_help(root.left, str);
            str = ser_help(root.right, str);
            return str;
        }
    
        public TreeNode deserialize(String data) {
            List<String> list_word = new LinkedList<String>(Arrays.asList(data.split(",")));
            return deser_help(list_word);
        }
        
        public TreeNode deser_help(List<String> li){
            if(li.get(0).equals("null")){
                li.remove(0);
                return null;
            }
            TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));
            li.remove(0);
            res.left = deser_help(li);
            res.right = deser_help(li);
            return res;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));

[20200310113307754.png]: https://img-blog.csdnimg.cn/20200310113307754.png
[20200310113327630.png]: https://img-blog.csdnimg.cn/20200310113327630.png
[20200310113337937.png]: https://img-blog.csdnimg.cn/20200310113337937.png