Мало знаний, большой вызов! Эта статья участвует в " Необходимые знания для программистов «Творческая деятельность
Эта статья также участвует "Проект "Звезда раскопок"" , чтобы выиграть творческие подарочные пакеты и бросить вызов творческим поощрениям
Код Пипи Креветка Глупый и забавный мальчик, который любит слушать песни и игры, как и большинство его друзей. Конечно, он также проявляет интерес к письму. Эмм..., дни еще длинные, давайте усердно работать вместе.🌈
Если вы считаете, что текст хороший, пожалуйста, подпишитесь на него 😉
предисловие
Обход бинарного дерева по соответствующему адресу:
Likou: адрес обхода предварительного заказа бинарного дерева
Likou: адрес обхода двоичного дерева по порядку
Likou: адрес обхода двоичного дерева в обратном порядке
Likou: адрес обхода порядка на уровне двоичного дерева
Обход порядка двоичного дерева
Используйте поиск в ширину (BFS)
public class Main {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
}
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;
}
}
рекурсия
Предварительный обход бинарного дерева
public class Main {
List<Integer> res;
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<>();
if(root == null)
return res;
preTreeNode(root);
return res;
}
private void preTreeNode(TreeNode root) {
if(root == null) return;
res.add(root.val);
preTreeNode(root.left);
preTreeNode(root.right);
}
}
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;
}
}
Анализ сложности
-
Временная сложность: O(n), где n — количество узлов в двоичном дереве. Каждый узел проходится ровно один раз.
-
Пространственная сложность: O(n), что является накладными расходами стека в рекурсивном процессе.В среднем это O(logn).В худшем случае дерево представляет собой цепочку, которая составляет O(n).
Неупорядоченный обход бинарного дерева
public class Main {
List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
if (root == null)
return res;
midTreeNode(root);
return res;
}
private void midTreeNode(TreeNode root) {
if (root == null) return;
midTreeNode(root.left);
res.add(root.val);
midTreeNode(root.right);
}
}
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;
}
}
Обход двоичного дерева в обратном порядке
public class Main {
List<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<>();
if(root == null)
return res;
postTreeNode(root);
return res;
}
private void postTreeNode(TreeNode root) {
if(root == null) return;
postTreeNode(root.left);
postTreeNode(root.right);
res.add(root.val);
}
}
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;
}
}
Итерационный метод
Предварительный обход бинарного дерева
Это почти то же самое, что и рекурсивный метод, но скрытый в рекурсии стек отображается
Из-за характеристик стека нам нужно сначала поместить в стек правый дочерний узел, а затем поместить левый дочерний узел, чтобы при его извлечении мы сначала вынимали левый дочерний узел.
public class Main {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}
}
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;
}
}
Неупорядоченный обход бинарного дерева
Неупорядоченный обход выводит узлы в левом среднем правом порядке. Итак, мы пытаемся запихнуть левое поддерево узла в стек, чтобы верхний элемент стека был самым левым узлом. После выталкивания вставьте в него его правый дочерний узел, в этом случае элементы обходятся по порядку.
public class Main {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null) {
cur = node.right;
}
}
return res;
}
}
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;
}
}
Обход двоичного дерева в обратном порядке
- Сначала поместите корневой узел в стек
- Поскольку сначала извлекается корневой узел, затем сначала извлекается правый дочерний узел, а затем левый дочерний узел извлекается последним.
- поместить левого дочернего элемента в стек
- поместите правильный дочерний элемент в стек
- Поскольку порядок всплывающих окон «коренной справа налево», необходимо каждый раз вставлять элементы в начало списка.
public class Main {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null)
stack.push(node.left);
if (node.right != null) {
stack.push(node.right);
}
result.add(0, node.val);
}
return result;
}
}
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;
}
}
💖Наконец
яКод Пипи Креветка, любитель креветок Пеппи, который любит делиться знаниями, в ближайшие дни продолжит обновлять посты в блоге, полезные для всех, и с нетерпением жду вашего внимания! ! !
Это не легко создать. Если этот пост в блоге полезен для вас, я надеюсь, что вы можете сделать три последовательных ссылки одним щелчком мыши! , спасибо за вашу поддержку, увидимся в следующий раз~~~