每日三题-翻转二叉树、二叉树的最近公共祖先、二叉树的序列化与反序列化

才疏学浅的木子

发布于 2022-11-18 14:02:56

2560

👨‍💻个人主页： 才疏学浅的木子 🙇‍♂️ 本人也在学习阶段如若发现问题，请告知非常感谢 🙇‍♂️ 📒 本文来自专栏： 算法 🌈 算法类型：Hot100题 🌈 ❤️ 支持我：👍点赞 🌹收藏 🤟关注

每日三题

补上11月11日的每日三题

翻转二叉树

解法一

递归

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        // 获取左节点
        TreeNode left = invertTree(root.left);
        //获取右节点
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

解法二

迭代

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while(!list.isEmpty()){
            TreeNode node = list.poll();
            TreeNode left = node.left;
            TreeNode right = node.right;
            node.left = right;
            node.right = left;
            if(node.left != null){
                list.add(node.left);
            }
            if(node.right != null){
                list.add(node.right);
            }
        }
        return root;
    }
}

二叉树的最近公共祖先

解法一

递归存在三种情况 p,q在root的两边，那么返回root p,q在root的一边。返回p或者q p,q不在，返回null

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;
    }
}

二叉树的序列化与反序列化

解法一

前序遍历

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        rserialize(root,sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        List<String> list = new ArrayList<>(Arrays.asList(split));
        return rdeserialize(list);
    }
    public void rserialize(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append("null,");
            return;
        }
        sb.append(root.val+",");
        rserialize(root.left,sb);
        rserialize(root.right,sb);
    }
    public TreeNode rdeserialize(List<String> list){
        if(list == null || list.size() == 0 || list.get(0).equals("null") || list.get(0).equals("")){
            list.remove(0);
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        node.left = rdeserialize(list);
        node.right = rdeserialize(list);
        return node;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树