Эта статья была впервые опубликована в моем личном блоге:племя хвост хвост
0. Несколько концепций
Полное бинарное дерево: если высота бинарного дерева равна h, за исключением h-го слоя, количество узлов в других (1~h-1) слоях достигло максимального числа, а узлы h-го слоя й слой постоянно концентрируется на крайнем левом. Думать о чем-то? На самом деле полное бинарное дерево и куча более тесно связаны~~~
Полное бинарное дерево: все узлы на каждом слое имеют двух дочерних элементов, кроме последнего слоя, а последний слой является конечным узлом.
Дерево Хаффмана: учитывая n весов в качестве листовых узлов n, постройте двоичное дерево. Если длина взвешенного пути достигает минимума, такое двоичное дерево называется оптимальным двоичным деревом, также известным как дерево Хаффмана. ).
Двоичное дерево сортировки: также известное как двоичное дерево поиска, также известное как двоичное дерево поиска. Бинарное отсортированное дерево — это либо пустое дерево, либо бинарное дерево со следующими свойствами:
Если левое поддерево не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
Если правое поддерево не пусто, значение всех узлов в правом поддереве больше или равно значению его корневого узла;
Левое и правое поддеревья также являются деревьями с бинарной сортировкой соответственно;
нет узлов с одинаковыми ключами
Временная сложность бинарного поиска составляет O (log (n)), а временная сложность в наихудшем случае - O (n) (эквивалентно последовательному поиску).
Сбалансированное двоичное дерево: также известное как дерево AVL. Сбалансированное бинарное дерево является эволюционной версией бинарного дерева поиска, так называемое сбалансированное бинарное дерево означает, что абсолютное значение разницы высот между левым и правым поддеревьями не превышает 1.
Красно-черное дерево: Красно-черное дерево — это дерево, в котором каждый узел окрашен, а цвет узла либо красный, либо черный.Красно-черное дерево — это дерево поиска. Важным свойством красно-черных деревьев является то, что самый длинный путь от корневого узла до конечного узла не более чем в два раза превышает длину кратчайшего пути. Для красно-черного дерева вставка, удаление и поиск выполняются за O(log N).
1. Найдите количество узлов в бинарном дереве
Рекурсивное решение:
(1) Если бинарное дерево пусто, количество узлов равно 0.
(2) Если оно не пусто, количество узлов бинарного дерева = количество узлов левого поддерева + количество узлов правого поддерева + 1
Справочный код выглядит следующим образом:
public static int getNodeNumRec(TreeNode root) {
if (root == null) {
return 0;
}
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}
2. Найдите максимальный уровень (максимальную глубину) бинарного дерева
Меч относится к предложению:глубина бинарного дереваРекурсивное решение:
(1) Если бинарное дерево пусто, глубина бинарного дерева равна 0
(2) Если бинарное дерево не пусто, то глубина бинарного дерева = max (глубина левого поддерева, глубина правого поддерева) + 1
Справочный код выглядит следующим образом:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}
2.1 Минимальная глубина бинарного дерева
LeetCode:Minimum Depth of Binary TreeДля заданного бинарного дерева найти его минимальную глубину.
Минимальная глубина — это количество узлов на кратчайшем пути от корневого узла до ближайшего конечного узла.
class Solution {
public int minDepth(TreeNode root) {
if(root == null)
return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
//采用逆序插入的方式
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}
Способ второй:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
TreeNode visited = null;
while(!stack.isEmpty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.peek();
if(cur.right != null && cur.right != visited){
cur = cur.right;
}else{
res.add(cur.val);
visited = cur;
stack.pop();
cur = null;
}
}
}
return res;
}
}
Способ 3 (рекомендуемый):
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null)
return res;
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> temp = new LinkedList<>();
for(int i=0; i<count; i++){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
}
// 每次都添加到第一个位置
res.add(0, temp);
}
return res;
}
}
6.2 Печать бинарного дерева в зигзагообразном порядке
Меч относится к предложению:Вывести бинарное дерево в зигзагообразном порядкеПожалуйста, реализуйте функцию печати бинарного дерева в виде зигзага, то есть первая строка печатается слева направо, второй слой печатается справа налево, третья строка печатается слева -вправо, а остальные строки печатаются слева направо и так далее.
Настройте два стека, s2 хранит слои с нечетными номерами, а s1 хранит слои с четными номерами.
Обходя узел s2, соедините s1 в порядке левого поддерева и правого поддерева,
Обходя узел s1, соедините s2 в порядке правого поддерева и левого поддерева.
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
int flag = 1;
if(pRoot == null)
return res;
s2.push(pRoot);
ArrayList<Integer> temp = new ArrayList<Integer>();
while(!s1.isEmpty() || !s2.isEmpty()){
if(flag % 2 != 0){
while(!s2.isEmpty()){
TreeNode node = s2.pop();
temp.add(node.val);
if(node.left != null){
s1.push(node.left);
}
if(node.right != null){
s1.push(node.right);
}
}
}
if(flag % 2 == 0){
while(!s1.isEmpty()){
TreeNode node = s1.pop();
temp.add(node.val);
if(node.right != null){
s2.push(node.right);
}
if(node.left != null){
s2.push(node.left);
}
}
}
res.add(new ArrayList<Integer>(temp));
temp.clear();
flag ++;
}
return res;
}
}
7. Найдите количество узлов в K-м слое бинарного дерева.
9. Определите, имеют ли два бинарных дерева одинаковую структуру
LeetCode:Same TreeИмея два бинарных дерева, напишите функцию, проверяющую, совпадают ли они.
Рекурсивное решение:
(1) Если оба бинарных дерева пусты, вернуть true
(2) Если одно из двух бинарных деревьев пусто, а другое не пусто, вернуть false
(3) Если оба двоичных дерева не пусты, если соответствующие левое поддерево и правое поддерево изоморфны, вернуть true, в противном случае вернуть false
10. Определите, является ли бинарное дерево сбалансированным бинарным деревом
LeetCode:Balanced Binary TreeУчитывая бинарное дерево, определите, является ли оно высоко сбалансированным.
Для этой задачи бинарное дерево со сбалансированной высотой определяется как: Бинарное дерево, в котором глубины двух поддеревьев каждого узла не отличаются более чем на 1.
Рекурсивное решение:
(1) Если бинарное дерево пусто, вернуть true
(2) Если двоичное дерево не пусто, если разница в высоте между левым поддеревом и правым поддеревом не больше 1, а левое поддерево и правое поддерево оба являются деревьями AVL, вернуть true, в противном случае вернуть false
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null)
return true;
return Math.abs(maxHigh(root.left) - maxHigh(root.right)) <= 1
&& isBalanced(root.left) && isBalanced(root.right);
}
public int maxHigh(TreeNode root){
if(root == null)
return 0;
return Math.max(maxHigh(root.left), maxHigh(root.right))+1;
}
}
Рекурсивное решение:
(1) Если два узла находятся в левом поддереве и правом поддереве корневого узла, вернуть корневой узел
(2) Если оба узла находятся в левом поддереве, рекурсивно обработать левое поддерево; если оба узла находятся в правом поддереве, рекурсивно обработать правое поддерево.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null)
return root;
return left == null ? right : left;
}
}
12.1 Поиск ближайшего общего предка бинарного дерева поиска
LeetCode:Lowest Common Ancestor of a Binary Search TreeУчитывая бинарное дерево поиска, найдите ближайшего общего предка двух заданных узлов в дереве.
Определение ближайшего общего предка в энциклопедии Baidu звучит так: «Для двух узлов p и q корневого дерева T ближайший общий предок представлен как узел x, который удовлетворяет тому, что x является предком p и q, а глубина x как можно больше. (Узел также может быть своим собственным предком)».
Обратите внимание на свойства бинарных деревьев поиска:左子树 < 根节点 < 右子树
LeetCode:Diameter of Binary TreeУчитывая бинарное дерево, вам нужно вычислить длину его диаметра. Диаметр бинарного дерева — это максимальная длина пути любых двух узлов. Этот путь может проходить через корневой узел.
Рекурсивное решение: для каждого узла его самый длинный путь равен самому длинному пути левого поддерева + самому длинному пути правого поддерева.
class Solution {
private int path = 0;
public int diameterOfBinaryTree(TreeNode root) {
diamHelper(root);
return path;
}
private int diamHelper(TreeNode root){
if(root == null)
return 0;
int left = diamHelper(root.left);
int right = diamHelper(root.right);
path = Math.max(path, left + right);
return Math.max(left, right) + 1;
}
}
14. Восстановите бинарное дерево из последовательности обхода в прямом порядке и последовательности обхода в неупорядоченном порядке.
Этот вопрос представляет собой процедуру с «Построение двоичного дерева из последовательности обхода в прямом и неупорядоченном порядке». Единственное отличие состоит в том, что последний узел последовательности пост-порядка является корневым узлом, поэтому мы должны начать с последнего узла последовательности пост-порядка, а затем перейти к последовательности порядка, чтобы найти этот узел. Левая часть этого узла принадлежит левой части поддерева корневого узла, а правая часть принадлежит правой части поддерева корневого узла. Затем в соответствии с количеством левых и правых узлов поддерева найдите их соответствующую пост-последовательность в пост-последовательности. Если число узлов в левом поддереве равно 5, то первые пять узлов в последовательности после последовательности являются узлами левого поддерева, а последующие узлы, кроме последнего узла, являются узлами правого поддерева.
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0)
return null;
return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
public TreeNode buildTreeHelper(int[] inorder, int in_start, int in_end,
int[] postorder, int post_start, int post_end){
if(in_start > in_end || post_start > post_end)
return null;
TreeNode root = new TreeNode(postorder[post_end]);
for(int i = in_start; i <= in_end; i++){
if(inorder[i] == postorder[post_end]){
root.left = buildTreeHelper(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1);
root.right = buildTreeHelper(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1);
}
}
return root;
}
}
Подсказка: уникальное двоичное дерево не может быть построено из обхода в прямом и обратном порядке.
15. Определите, является ли бинарное дерево полным бинарным деревом
Полное бинарное дерево означает, что левая сторона последнего слоя заполнена, правая сторона может быть медленной, но не полной, а затем остальные слои заполнены.Согласно этой функции используется обход слоя. Если мы в настоящее время переходим к узлу NULL, если в будущем будут узлы, отличные от NULL, это означает, что это неполное двоичное дерево.
17. Путь в бинарном дереве, который суммируется со значением
Меч относится к предложению:Путь в бинарном дереве, который суммируется со значениемВведите бинарное дерево и целое число, выведите все пути в бинарном дереве, сумма значений узлов которых является входным целым числом. Путь определяется как путь от корневого узла дерева до узлов, пройденных конечными узлами.
public class Solution {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> temp = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if(root == null)
return res;
target -= root.val;
temp.add(root.val);
if(target == 0 && root.left == null && root.right == null)
res.add(new ArrayList<Integer>(temp));
else{
FindPath(root.left, target);
FindPath(root.right, target);
}
temp.remove(temp.size()-1);
return res;
}
}
18. Следующий узел бинарного дерева
Меч относится к предложению:следующий узел в бинарном деревеИмея бинарное дерево и узел в нем, найдите следующий узел в порядке обхода и вернитесь. Обратите внимание, что узлы в дереве содержат не только левые и правые дочерние узлы, но и указатели на родительские узлы.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return "#,";
StringBuffer res = new StringBuffer(root.val + ",");
res.append(serialize(root.left));
res.append(serialize(root.right));
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String [] d = data.split(",");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < d.length; i++){
queue.offer(d[i]);
}
return pre(queue);
}
public TreeNode pre(Queue<String> queue){
String val = queue.poll();
if(val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}
20. k-й узел бинарного дерева поиска
Меч относится к предложению:k-й узел бинарного дерева поискаДля заданного бинарного дерева поиска найти в нем k-й наименьший узел. Например, в (5, 3, 7, 2, 4, 6, 8) значение третьего наименьшего узла в порядке нумерации узлов равно 4.
Поскольку последовательность обхода бинарного дерева поиска для вывода сортируется, поэтому мы проходим, чтобы найти k-й узел, являющийся предметом запроса в соответствии с последовательностью узлов.
class Solution {
public int kthSmallest(TreeNode root, int k) {
if(root == null)
return Integer.MIN_VALUE;
Stack<TreeNode> stack = new Stack<>();
int count = 0;
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
TreeNode node = stack.pop();
count ++;
if(count == k)
return node.val;
p = node.right;
}
}
return Integer.MIN_VALUE;
}
}