树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等技术内容,立即学习