树、二叉树、树的遍历、树的序列化

简介: 树、二叉树、树的遍历、树的序列化


树Tree

二叉树Binary Tree

代码 - 定义树的结点

C++

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x)
    : val(x), left(nullptr), right(nullptr) {}
}

Java

public class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int val) {
    this.val = val;
    this.left = null;
    this.right = null; 
  } 
}

Python

class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left, self.right = None, None

二叉树的遍历

前序Pre-order: 根 – 左子树 - 右子树

中序In-order: 左子树 - 根 – 右子树

后序Post-order:左子树 - 右子树 – 根

层次序

树的遍历

先序、中序、后序一般用递归来求

树的先序遍历又称树的深度优先遍历

层次序一般借助队列来求

树的层序遍历又称树的广度优先遍历

广度优先遍历

实战

94.二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        seq = new ArrayList<Integer>();
        dfs(root);
        return seq;
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        seq.add(root.val);
        dfs(root.right);
    }
    List<Integer> seq;
}

589.N叉树的前序遍历

https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        seq = new ArrayList<Integer>();
        dfs(root);
        return seq;
    }
    void dfs(Node root) {
        if (root == null) return;
        seq.add(root.val);
        for(Node child : root.children) {
            dfs(child);
        }
    }
    List<Integer> seq;
}
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        seq = new ArrayList<Integer>();
        if(root == null) return seq;
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            seq.add(node.val);
            for(int i = node.children.size() - 1; i >=0; i--){
                stack.push(node.children.get(i));
            }
        }
        return seq;
    }
    List<Integer> seq;
}

429.N叉树的层序遍历

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Pair<Node, Integer>> q = new LinkedList<Pair<Node, Integer>>();
        List<List<Integer>> seq = new ArrayList<List<Integer>>();
        if (root == null) return seq;
        q.add(new Pair<Node, Integer>(root, 0));
        while (!q.isEmpty()) {
            Node node = q.peek().getKey();
            Integer depth = q.poll().getValue();
            if(depth >= seq.size()) seq.add(new ArrayList<Integer>());
            seq.get(depth).add(node.val);
            for(Node child : node.children) {
                q.add(new Pair<Node, Integer>(child, depth + 1));
            }
        }
        return seq;
    }
}

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

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<String> seq = new ArrayList<String>();
        dfs(seq, root);
        return String.join(",", seq);
    }
    void dfs(List<String> seq, TreeNode root) {
        if(root == null) {
            seq.add("null");
            return;
        }
        seq.add(Integer.toString(root.val));
        dfs(seq, root.left);
        dfs(seq, root.right);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        seq = data.split(",");
        curr = 0;
        return restore();
    }
    TreeNode restore(){
        if (seq[curr].equals("null")) {
            curr++;
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(seq[curr]));
        curr++;
        root.left = restore();
        root.right = restore();
        return root;
    }
    String[] seq;
    int curr;
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

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

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }
    TreeNode build(int l1, int r1, int l2, int r2) {
        if(l1 > r1) return null;
        TreeNode root = new TreeNode(preorder[l1]);
        int mid = l2;
        while (inorder[mid] != root.val) mid++;
        root.left = build(l1 + 1,l1 + (mid - l2), l2, mid - 1);
        root.right = build(l1 + (mid - l2) + 1, r1, mid + 1, r2);
        return root;
    }
    int[] preorder;
    int[] inorder;
}

106.从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了,就结束
        if (in_left > in_right) {
            return nullptr;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;
        // 建立(元素,下标)键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

注意:从前序与后序遍历序列,并不能唯一-确定一棵二叉树

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习


相关文章
|
6月前
|
Go
golang力扣leetcode 297.二叉树的序列化与反序列化
golang力扣leetcode 297.二叉树的序列化与反序列化
40 0
|
存储 算法 Python
Python算法——树的序列化与反序列化
Python算法——树的序列化与反序列化
195 1
|
6月前
|
存储 算法 C++
leetcode-297:二叉树的序列化与反序列化
leetcode-297:二叉树的序列化与反序列化
44 1
|
3月前
|
存储 算法 Python
【Leetcode刷题Python】297. 二叉树的序列化与反序列化
LeetCode第297题"二叉树的序列化与反序列化"的Python语言解决方案,包括序列化二叉树为字符串和反序列化字符串为二叉树的算法实现。
25 5
|
6月前
|
Java Go 算法
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
54 0
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
|
6月前
|
Go Python 算法
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
767 0
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
|
6月前
|
算法 前端开发
331. 验证二叉树的前序序列化
331. 验证二叉树的前序序列化
48 0
|
6月前
|
算法
剑指 Offer 37:序列化二叉树
剑指 Offer 37:序列化二叉树
41 0
|
算法
【LeetCode力扣】297. 二叉树的序列化与反序列化
【LeetCode力扣】297. 二叉树的序列化与反序列化
65 0
|
10天前
|
JSON 数据格式 索引
Python中序列化/反序列化JSON格式的数据
【11月更文挑战第4天】本文介绍了 Python 中使用 `json` 模块进行序列化和反序列化的操作。序列化是指将 Python 对象(如字典、列表)转换为 JSON 字符串,主要使用 `json.dumps` 方法。示例包括基本的字典和列表序列化,以及自定义类的序列化。反序列化则是将 JSON 字符串转换回 Python 对象,使用 `json.loads` 方法。文中还提供了具体的代码示例,展示了如何处理不同类型的 Python 对象。