力扣二叉树部分题目题解---基本完成啦~

二叉树

前言：

对于树一直是有一种惧怕心理的，题目做的不够多，有思路都不知道怎么实现，希望通过这次二叉树的专项练习，可以入个门吧~~~：）

1.二叉树展开为链表

描述：把一棵二叉树展开为一条链表，链表的顺序就是二叉树的先序遍历顺序，链表实际上就是特殊的二叉树
总体说明：
- 在原先基础上建立链表
  - 迭代，划分为三大模块再处理里面的内容（解法一）
  - 先序遍历的逆过程，递归（解法二）
  - 栈保存左右子树信息（解法三）
- 新建链表（先序遍历保存下来，再形成链表）（解法四）
  - 递归或者的迭代的方式进行先序遍历依次保存节点

解法一：

思路：按照先序遍历的思路直接在二叉树上做修改（迭代），先是根节点，然后是左子树，最后是右子树；迭代每个根节点，把右子树挂到左子树的最右子节点，然后把左子树移到右子树的位置，原先的左子树置空。
代码：

class Solution {
    public void flatten(TreeNode root) {
       while(root != null){
           if(root.left == null){
               root = root.right;
           }else{
               TreeNode tmp = root.left;
               while(tmp.right != null){ //遍历找到左子树的最右子节点
                   tmp = tmp.right;
               }
               tmp.right = root.right;
               root.right = root.left;
               root.left = null;
               root = root.right;
           }
       }
    }
}

总结：根据先序遍历，把根节点，左子树，右子树先作为三个part连成一个链表，然后再依次迭代里面的内容

解法二

思路：先序遍历的逆过程。如果从根节点开始按照先序遍历的顺序直接建立链表，那么它的右节点就会还没有遍历到就直接被覆盖掉了。所以转换思维，从链尾开始倒着建立链表（root.right=pre,root.left=null）pre是链表上当前root的后一个节点，根据先右子树后左子树的递归，自底向上倒序连接形成链表。
代码：

class Solution {
    TreeNode pre;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = pre;
        root.left = null; 
        pre = root;
    }
}

总结：很棒的想法，通过递归实现的顺序是右子树，左子树，根节点，刚好是先序遍历（根节点，左子树，右子树）的逆序，再逐步组织链表。

解法三：

思路：之前提到直接按照先序遍历建立链表会覆盖掉原先的右子树，那么可以通过栈的方式保存子树信息，先存右子树，再存左子树，申明一个前置节点，刚开始是root,从栈中先取出来的是左子树的根节点，pre.right = cur; pre.left = null;然后更新pre即可。最终实现自顶向下建立链表。
代码：

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode pre = null;
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(pre != null){
                pre.right = cur;
                pre.left = null;
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
            pre = cur;
        }
    }
}

总结：递归迭代这些好像经常可以和栈联系起来，栈的作用主要是保存状态，使得程序的遍历可以更加符合**顺序逻辑**。

解法四：

思路：以上的方法都是直接在二叉树上修改，使之变成链表，实际上也可以直接申明一个List 类型的list,先序遍历二叉树，把节点按顺序放入list，最后连接起一个链表即可。

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preorderTraversal(root, list);
        for(int i = 0; i < list.size()-1; i++){ //List类型转为单向链表
            TreeNode cur = list.get(i), next = list.get(i + 1);
            cur.right = next;
            cur.left = null;
        }
    }
    public void preorderTraversal(TreeNode root, List<TreeNode> list){
        if(root != null){
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

总结：对于这种简单的递归要尽可能地熟练，并不难。

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

描述：给定一个升序数组，将其转化为一个高度平衡的二叉搜索树，即中序遍历是个升序数组

解法一：

思路：高度平衡，考虑把中间位置作为根节点进行建树，再递归调用建立左右子树即可。
代码：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = (left + right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid -1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}

总结：数组转化为二叉树思路并不难，只是对树的建立过程不够熟悉。因为涉及递归，最好新建一个函数。

3.二叉树的最近公共祖先

描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

解法一：

思路：通过递归分别去左右子树寻找，一旦找到p或q，直接返回，或者两者分别在左右子树，返回当前的root
代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}

总结：很精彩的递归，尤其是return root 这里，空的会向上传，直到有一个left和right都恰好是非空。

解法二：

思路：先提前dfs整棵树，确定所有的父节点，然后找出p的父节点这条路，再找q的所有祖先，一旦之前找到过，就是最近的公共祖先。另外，题目说明所有 Node.val 互不相同 ，故可以Map存储节点的值。
代码：

class Solution {
    Map<Integer, TreeNode> parent = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    public void dfs(TreeNode root){
        if(root.left != null){
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if(root.right != null){
            parent.put(root.right.val, root);
            dfs(root.right);
        }

 	   }
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p != null){
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while(q != null){
            if(visited.contains(q.val)){
                return q;
            }
            q = parent.get(q.val);
       }
        return null;
    }
}

总结：这个代码相对递归更好理解，就是直观的解法，后面的p，q就不是这两个点了，而是它们所有直接祖先这条线上的点。

4.把二叉搜索树转化为累加树

描述：给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。补充：二叉搜索树的中序遍历是一个升序数组。

解法一：

思路：逆向思维，从二叉搜索树的最右子节点开始，以中序遍历的逆过程（右子树，根节点，左子树）遍历，其值就是当前遍历过的节点的不断累加。
代码：

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}

总结：增加了递归的熟练度，宏观来看就是右子树，根节点，左子树的顺序，具体的实现细节也要验证符合要求，很锻炼思维能力。

5.路径总和|||

描述：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解法一：

思路：路径是从父节点到根节点，那么可以深度搜索遍历整棵树，同时维护一个前缀和的哈希数组，键是当前节点之前出现过的前缀和，值出现的次数，cur代表从根节点到达当前节点的所有的和。
代码

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }
    public Integer dfs(TreeNode root, Map<Long, Integer> prefix, long cur, int targetSum{
        if(root == null) return 0;
        int ret = 0;  //ret每次进来重新赋值，但由于下面的+=,最后会累加成最终的结果
        cur += root.val;
        ret = prefix.getOrDefault(cur - targetSum,0);
        prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
        ret += dfs(root.left, prefix, cur, targetSum);
        ret += dfs(root.right, prefix, cur, targetSum);
        prefix.put(cur,prefix.getOrDefault(cur, 0) - 1); //跳转到另一颗子树，必须恢复现场
        return ret;
    }
}

总结：二叉树还是跟递归关系很大，主要是利用了前缀和的思想和Map这一键值对的数据结构，还有就是当当前节点遍历完，换到另一颗子树时一定要恢复现场，才能保证prefix的准确性。

6.二叉搜索树中第K小的元素

描述：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解法一：

思路：二叉搜索树的特点是中序遍历是一个升序数组，那么直接进行中序遍历，保存到数组里，取第k个元素的值即可，是自己写出来的一道题呦~o(￣▽￣)ブ
代码：

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<TreeNode> list = new ArrayList<>();
        middleOrderTravesal(root,list);
        return list.get(k-1).val;
    }
    public void middleOrderTravesal(TreeNode root, List<TreeNode> list){
        if(root == null) return;
        middleOrderTravesal(root.left, list);
        list.add(root);
        middleOrderTravesal(root.right, list);
        return;
    }
}

总结：二叉树果然还是和递归或者遍历分不开，做多了就渐渐有感觉了。

7.二叉树的右视图

描述：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解法一：

思路：先右子树后左子树地递归，维护一个深度变量，如果是第一次到达该层就添加进答案，这样就满足右视图的要求了。
代码：

class Solution {
    int dep = 0;
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> right_view = new ArrayList<>();
        if(root == null) return right_view;
        dfs(root, right_view, 0);
        return right_view;
    }
    public void dfs(TreeNode root, List<Integer> right_view, int depth){
        if(root == null) return;
        depth++;
        if(depth > dep){
            right_view.add(root.val);
            dep = depth;
        }
        dfs(root.right, right_view, depth);
        dfs(root.left, right_view ,depth);
    }
}

总结：刚开始没有想到有可能右子树不存在，看到的是左子树的节点。所以需要维护一个深度，这部分有点思路但不太会实现，实际上就是通过一个全局变量来找到该层出现的第一个节点。

8.二叉树中的最大路径和

描述：二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

解法一：

思路：首先，这是个可递归的问题，对于每个节点，可以递归找到以它为根节点的且向下的路径和的最大值，那么对于整体的二叉树的最大路径和，可以在递归过程中，不断比较节点的值加上其左右子节点的最大路径和，最终找到最大路径和。由于存在负数，要和0比较一下。
代码：

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode node){
        if(node == null) return 0;
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0,maxGain(node.right));
        maxSum = Math.max(maxSum, node.val + leftGain + rightGain); //递归完后就可以把该节点作为候选节点
        return node.val + Math.max(leftGain, rightGain);
    }
}

总结：感觉以前好像做过，但是对于递归的熟悉还是不够，相当于把最终的路径按最上面的节点进行拆分为三个部分（当前节点，左子树的一条最大路径，右子树的一条最大路径），那么问题就转变为递归每个节点的最大贡献值。通过拆分把复杂问题简单化。

9、二叉树的直径

描述：给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。

解法一：

思路：直径可以不通过根节点，即答案的最高点可以不是根节点，那么ans就需要在这个过程中不断比较产生。递归得到以当前节点为根的左右两边的最大长度，尝试更新ans，并选取较大的一个返回给上层，这一点跟题目8很像。
代码：

class Solution {
    int ans = 1;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans - 1;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left) + 1;
        int right = dfs(root.right) + 1;
        ans = Math.max(ans, left + right -1);
        return Math.max(left, right);
    }
}

总结：慢慢自己调出了ac代码，这个过程还是很重要的，对于一些细碎的分类会更加清楚，比如需不需要全局变量，dfs需不需要返回值，+1-1这些判断，自己思考后会很清晰。

10.验证二叉搜索树

描述：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。

解法一：

思路：刚开始暴力的想法就是按照中序遍历的方式保存所有节点信息，再判断是否是一个升序数组，实际上可以直接在递归的过程中逐步地判断，对于当前的每个节点都有上一层传下来的上下界，不符合条件即可返回false。
代码：

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root, long lower, long upper){
        if(root == null) return true;
        if(root.val <= lower || root.val >= upper) return false;
        return isValidBST(root.left, lower, root.val) && 
        isValidBST(root.right, root.val, upper);
    }
}

总结：这个题目的递归顺序没有特别大的要求，主要是传参递归，并且参数是在不断修改的。另外，树上的递归一般都需要一个最先的if判断终止条件，以防递归的无限衍生。

11.二叉树的层序遍历

描述：给你二叉树的根节点 root ，返回其节点值的层序遍历 。（即逐层地，从左到右访问所有节点）。

解法一：

思路：按照题目按层取出节点值，想到广度优先搜索天然符合，通过队列来实现，先考虑左节点再考虑右节点，那么取出来就是每层的从左到右。
代码：

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

    }
}

总结：对于广度优先搜索太久没写了，主要就是用队列，刚开始放一个初始节点，然后非空判断，取出节点又再放入新的节点，并不难。

12.对称二叉树

描述：给你一个二叉树的根节点 root ，检查它是否轴对称。

解法一：

思路：可以采用迭代，利用队列来实现，不断地更新当前的u,v
代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    public boolean check(TreeNode u, TreeNode v){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(u);
        queue.offer(v);
        while(!queue.isEmpty()){
           u = queue.poll();
           v = queue.poll();
           if(u == null && v == null) continue;
           if(u == null || v == null || u.val != v.val) return false;
           queue.offer(u.left);
           queue.offer(v.right);
           queue.offer(u.right);
           queue.offer(v.left);
        }
        return true;
    }
}

总结：好像用到队列的写法都比较类似，只不过这道题没有涉及广搜的思想，主要就是实现一个迭代，和深搜的递归可以相互转化。

解法二：

思路：采取递归的方式，不断往下迭代。
代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }
    public boolean dfs(TreeNode u, TreeNode v){
        if(u == null && v == null ) return true;
        if(u == null || v == null || u.val != v.val) return false;
        return dfs(u.left, v.right) && dfs(u.right, v.left);
    }
}

总结：很精妙的递归题目，简单的代码即可实现。

13.翻转二叉树

描述：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解法一：

思路：通过经典的三点交换两个对象的值，然后递归向下逐层进行翻转。
代码：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

总结：特别的点在于方法虽然有返回值，但是在递归调用时不需要返回值，根据题意就是返回根节点即可，而根节点是不变的，最后原样返回即可。

14.从前序与中序遍历序列构造二叉树

描述：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解法一：

思路：前序与中序遍历相结合，通过前序遍历找到根节点，再通过该根节点在中序遍历中找到左子树的大小，进而回到前序遍历找到新的根，不断向下递归实现整棵二叉树的构造。
代码：

class Solution {
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int pl, int pr, int il, int ir){
        if(pl > pr) return null;
        int p_root = pl;
        int i_root = indexMap.get(preorder[p_root]);

        TreeNode root = new TreeNode(preorder[p_root]);
        int size_left_subtree = i_root - il;
        root.left = myBuildTree(preorder, inorder, pl + 1, pl + size_left_subtree, il, ir -1);
        root.right = myBuildTree(preorder, inorder, pl + size_left_subtree + 1, pr, i_root + 1, ir);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<Integer,Integer>();
        for(int i = 0; i < n; i++){
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

总结：找到其中可递归的部分，两个数组交相更新，很巧妙的一个出题思路。同时，利用了Map数据结构，快速找到其中的值的坐标。

15.打家劫舍|||

描述：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

解法一：

思路：是一个树形DP问题，每个节点有选（f）或不选(g)两种选择，自底向上看的话，f(node) = node.val+g(node.left)+g(node.right),g(node)=max(g(node.left),f(node.left))+max(g(node.right),f(node.right))。先递归再处理值的转移，就形成自底向上的推导。
代码：

class Solution {
    Map<TreeNode, Integer> f = new HashMap<>();
    Map<TreeNode, Integer> g = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root,0), g.getOrDefault(root,0));
    }
    public void dfs(TreeNode node){
        if(node == null) return;
        dfs(node.left);
        dfs(node.right);
        f.put(node,node.val + g.getOrDefault(node.left,0) + g.getOrDefault(node.right,0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0),g.getOrDefault(node.left, 0))
        +Math.max(f.getOrDefault(node.right, 0),g.getOrDefault(node.right, 0)));
    }
}

总结：第一眼都没看出来是动态规划。其实是个比较常见的自底向上的套路，推导公式也比较正常，结合Map实现，多多练习吧。

解法二：

思路：解法一的代码可以发现f,g和总是依赖上一层的结果，没必要记录所有的过程，可以对此进行优化，利用数组记录每次的结果即可。
代码：

class Solution {
    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }
    public int[] dfs(TreeNode node){
        if(node == null){
            return new int[]{0, 0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int select = node.val + l[1] + r[1];
        int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{select, noSelect};
    }
}

总结:利用数组的两个元素进行优化，代码原理基本一致，dfs有了返回值，相同的思路不一样的写法，That‘s cool.

16.二叉树的中序遍历

描述：给定一个二叉树的根节点 root ，返回 它的中序遍历 。

解法一：

思路：中序遍历即按照左子树、根节点、右子树的顺序递归遍历整棵二叉树
代码：

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        dfs(root.left);
        res.add(root.val);
        dfs(root.right);
    }
}

总结：分析dfs特点，选择设定一个全局变量，dfs不需要返回值。自己敲出来了，算是对树的递归入了门啦。当然，也可以把res作为一个参数传入到dfs中，是一样的效果。

解法二：

思路：使用迭代的思维，维护一个栈，先后加入左子树，直到不能加入为止，再加入根节点，再加入右子树，回到之前的步骤
代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stk = new LinkedList<>();
        while(root != null || !stk.isEmpty()){
            while(root != null){
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;

    }
}

总结：递归和迭代在很多时候可以相互转换，相对来说，对迭代更加不熟悉，需要多加练习。大部分是结合栈来实现，如第1题，但第12题对称二叉树采用了队列实现。

17.二叉树的最大深度

描述：给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解法一：

思路：很递归的一道题目，左右子树的最大深度又可以决定当前的最大深度
代码：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.max(l,r) + 1;
    }
}

总结：递归很清晰的一道题目，算是很多题目的源头叭~

18.二叉树的序列化和反序列化

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

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

解法一：

思路：可以按照先序遍历取出二叉树上的值，空节点用None代替，然后再把List类型递归按先序遍历生成二叉树
代码：

public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);   
    }
    public String rserialize(TreeNode root, String str){
        if(root == null){
            str += "None,";
        }else{
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }
    public TreeNode rdeserialize(List<String> dataList){
        if(dataList.get(0).equals("None")){
            dataList.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
        return root;
    }
}

总结：相当于两个简单题的组合，读取二叉树和将有序数组转化为二叉树，还有一些字符串的应用，比如valueOf,split方法

算法

#二叉树

力扣二叉树部分题目题解---基本完成啦~

http://example.com/2024/01/20/力扣算法题/力扣二叉树部分题目总结/

作者

jhxxxxx

发布于

2024年1月20日

许可协议

SpringBoot-demo-HelloWorld 上一篇

课设复盘下一篇