Table of Contents
-
是由n（n>0）个有限节点组成一个具有层次关系的集合。
如上图，就是两棵树
一个个小圆圈是一个节点，其中
节点1和节点2、节点3相差一个阶度，节点1是节点2和节点3的父节点，节点2和节点3是节点1的子节点，节点2与节点3又互称为兄弟节点 -
- 每个节点都只有有限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
- 树里面没有环路(cycle)
-
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
-
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
-
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
有序树中存在一种特殊的树，叫做二叉树
-
二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；所有叶节点都在最底层的完全二叉树又称为
满二叉树； - 平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
如图所示，就是两个二叉树
- 完全二叉树：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；所有叶节点都在最底层的完全二叉树又称为
-
-
前序遍历： 中左右 -
中序遍历： 左中右 -
后序遍历： 左右中 -
层序遍历
前序遍历：1、2、4、8、9、5、10、3、6、7 中序遍历：8、4、9、2、10、5、1、6、3、7 后序遍历：8、9、4、10、5、2、6、7、3、1 层序遍历：1、2、3、4、5、6、7、8、9、10以上图为例，分别进行四种遍历
以下是代码以及注释
递归法：
class Solution { public: // 定义结果数组 vector<int> res; vector<int> preorder(Node *root) { // 使用递归方法进行前序遍历 forward(root); return res; } void forward(Node *root) { // 如果当前的节点是空节点，就直接结束递归 if (root == nullptr) return; // 将当前节点的 val 值加入结果数组之中 res.push_back(root->val); // 遍历当前节点的 children 节点数组， // 依次进行遍历，并且继续向下进行递归 for (Node *node: root->children) forward(node); } };
class Solution { // 定义结果数组 List<Integer> res = new ArrayList<>(); public List<Integer> preorder(Node root) { // 使用递归方法进行前序遍历 forward(root); return res; } public void forward(Node root) { // 如果当前的节点是空节点，就直接结束递归 if (root == null) return; // 将当前节点的 val 值加入结果数组之中 res.add(root.val); // 遍历当前节点的 children 节点数组， // 依次进行遍历，并且继续向下进行递归 for (Node node : root.children) forward(node); } }
迭代法
class Solution { public: vector<int> preorder(Node *root) { // 定义结果数组 vector<int> res; // 如果 root 是空的话，就无需遍历，直接返回空数据即可 if (root == nullptr) return res; // 创建存储 node 节点的 栈 st stack<Node *> st; // 将首个节点 放入栈中 st.push(root); // 不停进行迭代直到 栈为空 while (!st.empty()) { // 从栈中取出最上方的节点，并将其移除栈中 Node *node = st.top(); st.pop(); // 将节点对应的 val 值放入结果数组中 res.push_back(node->val); // 倒序遍历当前节点的 children 序列， // 将其放入栈中，继续进行迭代 for (int i = node->children.size() - 1; i >= 0; i--) st.push(node->children[i]); } return res; } };
class Solution { public List<Integer> preorder(Node root) { // 定义结果数组 List<Integer> res = new ArrayList<>(); // 如果 root 是空的话，就无需遍历，直接返回空数据即可 if (root == null) return res; // 创建存储 node 节点的 栈 st Deque<Node> de = new ArrayDeque<>(); // 将首个节点 放入栈中 de.push(root); // 不停进行迭代直到 栈为空 while (!de.isEmpty()) { // 从栈中取出最上方的节点，并将其移除栈中 Node node = de.pop(); // 将节点对应的 val 值放入结果数组中 res.add(node.val); // 倒序遍历当前节点的 children 序列， // 将其放入栈中，继续进行迭代 for (int i = node.children.size() - 1; i >= 0; i--) de.push(node.children.get(i)); } return res; } }
由于N叉树的中序遍历没有很明确的定义，这里就以二叉树的中序遍历为例
递归法：
class Solution { public: // 定义结果数组 vector<int> res; vector<int> inorder(Node *root) { // 使用递归方法进行中序遍历 inward(root); return res; } void inward(Node *root) { // 如果当前的节点是空节点，就直接结束递归 if (root == nullptr) return; // 模拟左中右的方式 // 探寻左节点 inward(root->left); // 将当前节点的 val 值加入结果数组之中 res.push_back(root->val); // 探寻右节点 inward(root->right); } };
class Solution { // 定义结果数组 public ArrayList<Integer> res = new ArrayList<>(); public List<Integer> inorder(Node root) { // 使用递归方法进行中序遍历 inward(root); return res; } void inward(Node root) { // 如果当前的节点是空节点，就直接结束递归 if (root == null) return; // 模拟左中右的方式 // 探寻左节点 inward(root.left); // 将当前节点的 val 值加入结果数组之中 res.add(root.val); // 探寻右节点 inward(root.right); } }
迭代法：
class Solution { public: vector<int> inorderTraversal(Node* root) { // 创建结果数组 vector<int> res; // 创建栈，以用来存放节点 stack<Node*> st; // 进入迭代 while (root != nullptr || !st.empty()) { // 首先先将左节点压入 栈 中 // 原因：中序遍历首先是以 左节点开始的，首先要找到最左端的节点 while (root != nullptr) { st.push(root); root = root->left; } root = st.top(); st.pop(); // 压入相应的值 res.push_back(root->val); // 然后遍历右侧节点 root = root->right; } return res; } };
class Solution { public List<Integer> inorderTraversal(Node root) { // 创建结果数组 ArrayList<Integer> res = new ArrayList<>(); // 创建栈，以用来存放节点 ArrayDeque<Node> st = new ArrayDeque<>(); // 进入迭代 while (root != null || !st.isEmpty()) { // 首先先将左节点压入 栈 中 // 原因：中序遍历首先是以 左节点开始的，首先要找到最左端的节点 while (root != null) { st.add(root); root = root.left; } root = st.pop(); // 压入相应的值 res.add(root.val); // 然后遍历右侧节点 root = root.right; } return res; } }
递归法
class Solution { public: vector<int> postorder(Node *root) { vector<int> res; dfs(root, res); return res; } void dfs(Node *root, vector<int> &res) { if (root == nullptr) return; for (auto &node: root->children) { dfs(node, res); } res.push_back(root->val); } };
class Solution { public List<Integer> postorder(Node root) { List<Integer> list = new ArrayList<>(); dfs(root, list); return list; } void dfs(Node root, List<Integer> list) { if (root == null) return; for (Node node : root.children) { dfs(node, list); } list.add(root.val); } }
迭代法
class Solution { public: vector<int> postorder(Node *root) { vector<int> res; if (root == nullptr) return res; // 创建一个队列 来执行迭代 stack<Node *> st; // 创建一个 HashSet 来统计 每个节点的子节点是否完全被遍历过一次 unordered_set<Node *> cnt; st.push(root); // 不停的循环，直到 栈中的元素为空 while (!st.empty()) { // 取栈中的顶层元素进行判断 Node *temp = st.top(); // 如果 其没有 children 序列 // 或者 其子序列已经被遍历过一次 // 就进行统计 // 并将其移除 if (temp->children.size() == 0 || cnt.count(temp)) { res.push_back(temp->val); st.pop(); continue; } // 如果其子节点序列不为空 // 或者仍未访问过，则将其子节点序列压入栈中 // 等待下一次迭代 // 由于我们统计是从左到右顺序统计，因此我们在压入栈中的时候要倒序压入，以便后续迭代 for (auto it = temp->children.rbegin(); it != temp->children.rend(); it++) { st.push(*it); } // 此节点其子节点已经被遍历过了，因此放入 HashSet 中进行标记 cnt.insert(temp); } return res; } };
class Solution { public List<Integer> postorder(Node root) { List<Integer> res = new ArrayList(); if (root == null) return res; // 创建一个队列 来执行迭代 Deque<Node> st = new ArrayDeque<>(); // 创建一个 HashSet 来统计 每个节点的子节点是否完全被遍历过一次 Set<Node> cnt = new HashSet(); st.push(root); // 不停的循环，直到 栈中的元素为空 while (!st.isEmpty()) { // 取栈中的顶层元素进行判断 Node temp = st.peek(); // 如果 其没有 children 序列 // 或者 其子序列已经被遍历过一次 // 就进行统计 // 并将其移除 if (temp.children.size() == 0 || cnt.contains(temp)) { res.add(temp.val); st.pop(); continue; } // 如果其子节点序列不为空 // 或者仍未访问过，则将其子节点序列压入栈中 // 等待下一次迭代 // 由于我们统计是从左到右顺序统计，因此我们在压入栈中的时候要倒序压入，以便后续迭代 for (int i = temp.children.size() - 1; i >= 0; i--) st.push(temp.children.get(i)); // 此节点其子节点已经被遍历过了，因此放入 HashSet 中进行标记 cnt.add(temp); } return res; } }
层序遍历，顾名思义，按层，一层一层遍历
而递归的方法，他的思想是从头到尾，在深度的方向上进行解决
而这就与我们所希望的层序遍历的想法相反
那么我们就要在原有的基础上进行一些修改，使得最后呈现的效果是层序遍历
现在问题就到了如何保证同一层的各个子节点在一起，那么我们可以尝试在遍历子树的时候，将同一层的节点放在同一个列表中，因此在递归时要记录深度 depth。
同时，每次遍历到一个新的 depth，结果数组中没有对应的 depth 的列表时，在结果数组中创建一个新的列表保存该 depth 的节点。
粗略概括一下就是 创建一个二维数组 res ，然后通过不停的深入递归树(前序递归)，将对应深度的树的节点的值，加入到二维数组对应的位置中去
就拿上图为例：
首先到达根节点，当前深度为 1 ，就将 1 的值放入到 res[0] 的数组中 然后到达节点 2 ，当前那深度为 2 ，就将 2 的值放入 res[1] 中 然后到达节点 4 ，当前那深度为 3 ，就将 4 的值放入 res[3] 中 然后到达节点 8 ，当前那深度为 4 ，就将 8 的值放入 res[4] 中 然后到达节点 9 ，当前那深度为 4 ，就将 9 的值放入 res[4] 中 …………………… 以此类推具体代码以及注释如下
class Solution { public: // 创建数组统计各个节点 vector<vector<int>> res; void level(Node *root, int depth) { if (root == nullptr) return; // 如果 res 数组的长度要小于当前的深度 // 就说明我们需要继续向 res 数组中放入当前的深度的节点，同时还记录了 当前的深度 if (res.size() < depth) { res.push_back(vector<int>()); } // 由于树的深度是从 1 开始的 // 而数组的索引是从 0 开始的的 // 因此要在 depth -1 的位置插入 res[depth - 1].push_back(root->val); // 遍历子节点，将对应的值放入 相应的 res 数组之中 for (Node *child: root->children) { level(child, depth + 1); } } vector<vector<int>> levelOrder(Node *root) { level(root, 1); return res; } };
class Solution { // 创建数组统计各个节点 public List<List<Integer>> res = new ArrayList<>(); public void level(Node root, int depth) { if (root == null) return; // 如果 res 数组的长度要小于当前的深度 // 就说明我们需要继续向 res 数组中放入当前的深度的节点，同时还记录了 当前的深度 if (res.size() < depth) { res.add(new ArrayList<>()); } // 由于树的深度是从 1 开始的 // 而数组的索引是从 0 开始的的 // 因此要在 depth -1 的位置插入 res.get(depth - 1).add(root.val); // 遍历子节点，将对应的值放入 相应的 res 数组之中 for (Node child : root.children) { level(child, depth + 1); } } public List<List<Integer>> levelOrder(Node root) { level(root, 1); return res; } }
由于层次遍历的属性非常契合队列的特点，所以层次遍历用的是队列。
使用队列保存每一层的所有节点，把队列里的所有节点出队列，然后把这些出去节点各自的子节点入队列。以此来完成对每层的遍历。
class Solution { public: vector<vector<int>> levelOrder(Node *root) { // 首先创建结果数组 vector<vector<int>> res; // 如果树是空的，直接返回 空数组就行 if (root == nullptr) return res; // 如果树不是空的，就创建一个队列，用于进行后续的层序遍历 queue<Node *> qu; // 首先将根节点放入 栈中,以便后续迭代 qu.push(root); while (!qu.empty()) { vector<int> temp; // 统计当前 队列的长度 int len = qu.size(); for (int i = 1; i <= len; ++i) { // 返回队列中的第一个节点，并从队列中删除当前节点 Node *node = qu.front(); qu.pop(); // 向当前 数组中，加入相应的值 temp.push_back(node->val); // 相应的值添加完成以后将其子节点们，依次放入队列中，进行下一次的迭代 for (auto t: node->children) { qu.push(t); } } // 当一层的节点遍历完成后，将得到的结果加入 结果数组 res 之中 res.push_back(temp); } return res; } };
class Solution { public List<List<Integer>> levelOrder(Node root) { // 首先创建结果数组 List<List<Integer>> res = new ArrayList<List<Integer>>(); // 如果树是空的，直接返回 空数组就行 if (root == null) { return res; } // 如果树不是空的，就创建一个队列，用于进行后续的层序遍历 Queue<Node> queue = new LinkedList<Node>(); // 首先将根节点放入 栈中,以便后续迭代 queue.add(root); while (!queue.isEmpty()) { List<Integer> temp = new ArrayList<>(); // 统计当前 队列的长度 int len = queue.size(); for (int i = 1; i <= len; ++i) { // 返回队列中的第一个节点，并从队列中删除当前节点 Node node = queue.poll(); // 向当前 数组中，加入相应的值 temp.add(node.val); // 相应的值添加完成以后将其子节点们，依次放入队列中，进行下一次的迭代 queue.addAll(node.children); } // 当一层的节点遍历完成后，将得到的结果加入 结果数组 res 之中 res.add(temp); } return res; } }
-