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

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

    树Tree

    在这里插入图片描述

    二叉树Binary Tree

    在这里插入图片描述

    代码 - 定义树的结点

    C++

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    Java

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    Python

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

    • 1
    • 2
    • 3
    • 4

    二叉树的遍历

    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    589.N叉树的前序遍历
    https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/

    /*
// Definition for a Node.
class Node {
    public int val;
    public List children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List _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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    /*
// Definition for a Node.
class Node {
    public int val;
    public List children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List _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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    429.N叉树的层序遍历
    https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

    /*
// Definition for a Node.
class Node {
    public int val;
    public List children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List _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;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

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



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

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

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

  • 相关阅读:
    Vue - 虚拟DOM的简单理解
    UOS服务器操作系统搭建离线yum仓库
    【坚持不懈的每日一题——力扣篇】1796. 字符串中第二大的数字（简单）＋set 用法复习
    Day36 移动端自动化
    01-Spring底层核心原理解析
    【自然语言处理】【文本生成】CRINEG Loss：学习什么语言不建模
    1、Flutter使用总结(RichText、Container)
    零售数据分析方案：深度剖析人、货、场
    如何在 Vim 中剪切、复制和粘贴
    Linux磁盘扩容（加硬盘法）
  • 原文地址：https://blog.csdn.net/qq_46118239/article/details/126712758