[Веселый алгоритм] 31 алгоритм бинарного дерева, подарок себе на Первомай

предисловие

Недавно я сделал небольшое краткое изложение алгоритма дерева. Эти темы взяты из leetcode, которые представляют собой некоторые классические темы, представляющие идею алгоритма двоичного дерева.

Например高度平衡二叉树,二叉搜索树BST,tire树Равная структура данных, сначала глубина в ширину遍历,递归,迭代Алгоритмическое мышление. если для递归Если вы с ним не знакомы, можете посмотреть первую часть моего алгоритма.«Оливер Твист» полон картинок и текстов, алгоритм рукопашного боя, вы также можете оставить сообщение в комментариях, а Линлун ответит на вопросы братьев и сестер в следующую секунду😉.

Я тоже алгоритмический отморозок, я не мог понять смысла рекурсии, когда впервые увидел чужие объяснения, точно так же, как я не понял, почему машина пошла налево, когда я развернул машину и поставил руль. левый перед (закрывая лицо). В любом случае, я алгоритмический идиот. Но я думаю, что будут результаты, если я буду придерживаться этого, это всего лишь вопрос времени.

На самом деле, я два или три раза делал следующие вопросы, прежде чем смог решить их самостоятельно😅.С одной стороны, я хочу поделиться ими, чтобы дать ссылку на моих друзей, которые практикуют алгоритм.С другой стороны, это также является кратким изложением моего собственного алгоритма бинарного дерева (майский подарок самому себе).

Код в основномjavaScriptРеализация, ведь главное идея и код не сложный.Поскольку в последнем вопросе используется знание цепочки прототипов, я тоже использую последний вопрос.javaЯ написал это снова для справки друзей, не копающих интерфейс. Конечно, идея та же.

Основные понятия деревьев

Если вы знакомы со структурой деревьев, то просто посмотрите упражнения и начните свое путешествие по алгоритму 1 мая~

Введение концепции

• Полное бинарное дерево: полное бинарное дерево состоит в том, что каждый узел имеет левое поддерево и правое поддерево, а все конечные узлы находятся на одном уровне.
• Полное бинарное дерево: подмножество полного бинарного дерева.
• Сбалансированное бинарное дерево: разница высот между левым и правым поддеревьями узла не превышает 1, и появляются следующие темы
• Двоичное дерево поиска: упорядоченный обход двоичного дерева поиска, левый дочерний элемент меньше корневого узла, а правый дочерний элемент больше корневого узла.
• Дерево префиксов: дерево префиксов также называют деревом словарей.Энциклопедия Байду

Каждый узел может иметь 26 различных дочерних узлов, а значение узла равноa-z26 букв.

---

Кроме того, есть несколько основных понятий, которые можно использовать в качестве понимания:

• Степень узла: степень узла - это количество ветвей, испускаемых узлом, которые являются горизонтальными. Если количество выпущенных ветвей равно 0, то степень узла равна 0.
• Степень дерева: максимальное значение степени узла равно степени дерева.
• Глубина дерева: максимальный уровень узла равен глубине дерева.
• Уровень узла: количество ответвлений от корневого узла к данному узлу, в количестве только один узел, уровень узла 0

Эти четыре понятия относительны, и если их разделить на две категории, то их отличают от горизонтальных и вертикальных. Я просто назову это: "横度纵生". Смысл этих четырех символов в том, что степень узла представляет собой горизонтальное направление; степень глубины (необработанная) дерева представляет собой вертикальное направление.

2. Свойства бинарных деревьев

Хотя следующие вопросы по алгоритму используются редко, я думаю, что это базовая грамотность, которую необходимо знать.

• Свойство 1: i-й уровень непустого бинарного дерева имеет не более 2^i (наш i=0 для первого уровня).
• Свойство 2: Количество узлов в полном бинарном дереве равно 2^(k+1)-1. k — 0-й уровень иерархии узлов. Этот вывод можно рассчитать по пропорциональной последовательности.
• Листовое дерево узлов непустого бинарного дерева равно n0, а степень равна 2. Дерево узлов равно n2, тогда существует отношение n0=n2+1. Об этом можно судить по связи между внедрением ветвей и ввод ветвей и итоговая точка.

3. Обход бинарного дерева

Бинарное дерево состоит из трех частей: корневого узла, левого поддерева и правого поддерева. По порядку доступа к корневому узлу его можно разделить на три типа. То есть обход в предварительном порядке, обход по порядку и последующий обход. В дополнение к обходу по типу узла существует также обход по порядку слоев, который проходит по левому поддереву, а затем по правому поддереву на том же уровне.

• обход предварительного заказа Предварительный порядок обхода сначала обхода корневого узла, затем левого поддерева и, наконец, правого поддерева.
• Неупорядоченный обход Обход по порядку сначала обходит левое поддерево, затем корневой узел, а затем правое поддерево.
• последующий обход Последующие обходы сначала проходят по левому поддереву, затем по правому поддереву и, наконец, по корневому узлу.
• ps: предварительный обход и последующий обход не могут определить дерево. Например, предварительный заказ AB, последующий BA, не знаю, является ли дерево ABnull или AnulB
• Обход по уровням: Обход по уровням использует очереди, мышление в порядке поступления. Проходим слой за слоем. Корневой узел ставится в очередь, а первый элемент очереди вынимается.Если есть левый и правый узлы, то в очередь ставится левый и правый узлы, а затем вынимается первый элемент очереди ...пока очередь не опустеет. Это немного абстрактно, и мы рассмотрим такие вопросы, как 19, в сочетании с темами позже.

Нерекурсивная реализация обхода

С помощью реализации стека стек имеет характеристики «первым пришел — последним ушел». Нерекурсивная реализация обхода бинарного дерева в прямом порядке сначала помещает корневой узел в стек, вынимает элемент корневого узла, если левое поддерево не пусто, кладет левое поддерево в стек, а затем извлекает верхний элемент стека, чтобы увидеть, есть ли у элемента правильный узел, если да. Правый узел помещается в стек, а верхний элемент извлекается до тех пор, пока стек не станет пустым. Там также будут связанные вопросы, такие как 12 вопросов позже.

оригинальное название leetcode

основные свойства деревьев

Вопрос 1: Максимальная высота дерева - 104

• Вопрос: Для дерева верните максимальную высоту дерева, которая является глубиной дерева. следующим образом:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

• анализировать: Чтобы найти высоту дерева, мы можем найти высоту левого поддерева и высоту правого поддерева.Большее значение из двух + 1 - это высота текущего дерева. Высота левого поддерева может быть определена как большее из значений высоты левого поддерева и высоты правого поддерева + 1. Мы нашли закон рекурсии, когда мы вернемся? То есть при каких обстоятельствах есть выход, когда обход до узла пустой, он рекурсирует на последний уровень. Итак, root==null - это выход.

• решение проблем

var maxDepth = function(root) {
    if(root==null) return 0;
    return Math.max(maxDepth(root.left),  maxDepth(root.right) )+1;
};

Вопрос 2 - Сбалансированные деревья 110

• Тема: Здесь вы определяете, является ли дерево сбалансированным бинарным деревом.

Given a binary tree, determine if it is height-balanced.
Given the following tree [3,9,20,null,null,15,7]:
    3
   / \
  9  20
    /  \
   15   7

Сбалансированное бинарное дерево — это разница в высоте между левым и правым поддеревьями узла

• анализировать: Как и в предыдущем случае, рекурсивно найдите высоту левого и правого поддеревьев, а затем верните false, если разница в высоте между левым и правым поддеревьями больше 1, в противном случае — true. Итак, нам нужно знать当前结点左右子树的高度差<=1&&当前结点的左孩子的左右子树高度差<=1&&当前结点的右孩子的左右子树高度差<=1. Это верно, когда соблюдаются все три условия.
• Решение проблемы: Функция глубины находит высоту левого и правого поддеревьев.

var isBalanced = function(root) {
    if(root==null) return true;
    var cur= Math.abs(depth(root.left)-depth(root.right))>1? false : true;
    return cur&&isBalanced(root.left) && isBalanced(root.right);
}
function depth(root) {
if(root ==null) return 0;
var l = depth(root.left);
var r = depth(root.right);
return Math.max(l,r)+1
}

Вопрос 3 - Переверните дерево 226

• тема:

翻转一棵二叉树。
示例：
输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

LeetCode

• Анализ: его также можно реализовать рекурсивно, заменяя результат левого поддерева результатом отражения правого поддерева. Результат переворачивания левого поддерева является результатом перестановки левого-левого поддерева и правого-правого поддерева... до тех пор, пока левое и правое поддеревья последнего узла не станут пустыми и не будут возвращены.
• Решение проблем:

var invertTree = function(root) {
    if(!root) return null;
    //左子树是左子树反转后的结果
    root.left = invertTree(root.left);
    //右子树是右子树翻转的结果
    root.right = invertTree(root.right);
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    return root;
};

Вопрос 4 - Объединить два дерева 617

• тема:

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

LeetCode

• Анализ: слияние бинарных деревьев можно рассматривать как значение узла одного дерева плюс значение узла другого дерева. Используйте рекурсию. Результат сложения текущего значения узла + результат слияния левого поддерева + результат слияния правого поддерева — это окончательное возвращаемое дерево. Результат слияния левого поддерева = текущее значение узла левого потомка + результат слияния левого и левого поддеревьев + результат слияния правого и правого поддеревьев. Возврат до тех пор, пока все узлы на обоих деревьях не будут пройдены.
• Решение проблем:

var mergeTrees = function(t1, t2) {
   //如果左右子树都空
    if(!t1&&!t2) return null;
    //如果左右子树有一个空
    if(!t1||!t2) return t1||t2;
    t1.val = t1.val+t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
};

проблема пути к бинарному дереву

Вопрос 5 - Самый длинный путь дерева 543

• тема:

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

LeetCode

• Анализ: В этом вопросе нам нужно знать, что диаметр дерева — это максимальное значение от одного узла дерева до другого узла. В примере с заголовком нам легко неправильно понять, что максимальная длина — это высота левого поддерева + высота правого поддерева. Но это не совсем так.При обходе каждого узла нам необходимо зафиксировать максимальное значение текущего диаметра, а затем судить о максимальном значении следующего узла и размере текущего максимального значения.Если максимальный диаметр следующий узел больше максимального значения текущего значения, затем обновите максимальное значение.

Например, в следующем примере: диаметр узла, значение которого равно -5, равен 7, а диаметр корневого узла -9 равен 6. Таким образом, максимальный диаметр не обязательно является суммой глубины левого поддерева и глубины правого поддерева.

• решение проблем

var diameterOfBinaryTree = function(root) {
if(!root) return 0;
var max = 0;
function maxdepth(root){
    if(!root) return 0;
    var left = maxdepth(root.left);
    var right = maxdepth(root.right);
    //更新直径的最大值
    max = Math.max((left+ right),max);
    return Math.max(left, right)+1
}
maxdepth(root);
return max;
}

Сложность времени o (n): количество прохожденных узлов

Пространственная сложность O(высота): высота дерева

Вопрос 6 - Определите, равна ли сумма путей числу 112

• тема:

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 
给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

LeetCode

• Разбор: обход узлов дерева. Возвращает true, когда обход завершен и сумма всех пройденных узлов равна сумме
• Решение проблем:

<!--//错误的方法，不满足全局性：左子树如果不满足遍历完返回false不会遍历右子树-->
<!--var hasPathSum = function(root, sum) {-->
<!--    if(!root)return false;-->
<!--    if(root.val == sum&& root.left==null&&root.right==null) return true;-->
<!--    // return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right,sum-root.val);-->
<!--    if(!roo.left)hasPathSum(root.left, sum-root.val);-->
<!--    if(!root.right)hasPathSum(root.right,sum-root.val);-->
<!--};-->
//正确的解答
var hasPathSum = function(root, sum) {
    if(!root) return false;
    if(root.val == sum&& root.left==null&&root.right==null) return true;
    return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right,sum-root.val);
};

Вопрос 7 - Подсчитайте количество путей, которые дерево удовлетворяет требованиям 437

• тема:

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
返回 3。和等于 8 的路径有:
1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

LeetCode

• Анализ: Ядро также является обходом дерева в глубину, но этот обход другой, путь может начинаться с любого узла, поэтому каждый узел является корневым узлом. Возьмите приведенный выше пример, чтобы увидеть, что мы берем 10 в качестве корневого узла для прохождения и не можем найти тот, который соответствует требованиям, затем берем 5 в качестве корневого узла для прохождения и находим два пути, которые соответствуют требованиям, а затем берем 3 в качестве пути. корневой узел, чтобы увидеть, есть ли какие-либо требования....

  Итак, как посмотреть, выполнены ли требования, то есть равно ли значение текущего значения узла сумме, если оно равно, то группа найдена, а затем продолжить обход, чтобы найти все пути, удовлетворяющие требованиям вопрос, начиная с корневого узла. Это также рекурсия.Рекурсивное уравнение представляет собой количество путей, соответствующих требованиям count=удовлетворен ли корень корневого узлаvalue==sumУдовлетворяет ли &&root.left значение == sum-root.value&&root.right удовлетворяет ли value==sum-root.left. Соответствует функции пути.

• Решение проблем:

//双重递归
var pathSum = function(root, sum) {
    if(!root) return 0;
    function path(root, sum) {
       var count = 0;
        if(!root) return 0;
        if(root && root.val == sum) count++;
        count += path(root.left, sum-root.val)+path(root.right, sum-root.val);
        return count;
    }
    return  path(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum);
};

Вопрос 8 - Минимальный путь 111

• тема

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

LeetCode

• Анализ: Первое ощущение этой темы может быть таким же, как 104 для нахождения максимальной глубины.Если это так, то [1, 2] не выполняется, поэтому, когда одно из левого и правого поддеревьев равно нулю, оно должно взять ненулевое значение и добавить 1.
• Код

var minDepth = function(root) {
    if(!root) return 0;
    let l = minDepth(root.left);
    let r= minDepth(root.right);
    //取左或右子树有一个为0的时候取非0的值
    if(l==0&&r!=0||r==0&&l!=0) return (l||r)+1;
    return Math.min(l, r)+1;
};

• Временная сложность: мы посещаем каждый узел один раз, а временная сложность составляет O(N)O(N) , где NN — количество узлов.
• Сложность пространства: в худшем случае все дерево несбалансировано, например, у каждого узла есть только один дочерний элемент, рекурсия будет вызываться N (высота дерева) раз, поэтому накладные расходы пространства стека составляют O (N ). Но в лучшем случае дерево идеально сбалансировано и имеет высоту только log(N), поэтому пространственная сложность в этом случае составляет всего O(log(N)) .

Способ второй

Используется иерархический обход плюс двухуровневые циклы без обхода каждого узла. Когда текущий узел является конечным узлом, возвращается номер слоя текущего узла.

var minDepth = function(root) {
    if(!root) return 0;
    if(!root.left&&!root.right) return 1;
    let quene = [];//队列
    let level = 0;
    quene.push(root);
    while(quene.length){
        let size = quene.length
        while(size--){
            let cur = quene.shift();
            if(cur.left!=null){
                quene.push(cur.left);
            } 
            if(cur.right!=null) {
                quene.push(cur.right); 
            } 
            //找到叶子结点
            if(!cur.left&&!cur.right){
                return level+1;
            }
        }
        level++; 
    }
};

Вопрос 9-124 Статистическая максимальная сумма пути (сложный)

• тема

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
       1
      / \
     2   3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
输出: 42

LeetCode

• Анализ: В этом вопросе необходимо выяснить, что означает сумма путей, а не количество путей, а наибольшая сумма значений, проходящих через узлы После понимания смысла вопроса это одно и то же как 543 687. Может быть более строгим, что сумма путей не должна быть меньше 0, а максимальная сумма путей дерева может иметь отрицательное значение (когда значение узла отрицательное)
• решение проблем

var maxPathSum = function(root) {
let max = Number.MIN_SAFE_INTEGER;;
const path = (root) => {
    if(root == null) return 0;
    let left = Math.max(0,path(root.left));
    let right =Math.max(0,path(root.right)); 
    max = Math.max(max, left+right+root.val);
    // return left+right+root.val;不满足测试二
    return Math.max(left,right)+root.val;
}
path(root);
return max;
};

Вопрос 10 - Максимальная длина пути для одного и того же значения узла 687

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
              5
             / \
            4   5
           / \   \
          1   1   5
输出:
2
示例 2:
输入:
              1
             / \
            4   5
           / \   \
          4   4   5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

Источник: LeetCode

• Анализ: первая мысль в этой теме — двухуровневый рекурсивный обход, и каждый узел считается корневым узлом. Затем запишите текущее максимальное значение, сравните и обновите максимальное значение. Этот вопрос немного похож на максимальное количество путей, которое равно leetcode 543. Разница в том, что есть еще два параметра leftpath и rightpath для записи узлов с одинаковым значением, а возвращаемое значение другое, но общая идея та же. .
• решение проблем

var longestUnivaluePath = function(root) {
// //当前树的路径数
if(!root) return 0;
let max = 0;
const depth = (root)=>{
    if(!root) return 0;
    let left = depth(root.left);
    let right = depth(root.right);
    let leftpath = (root.left&&root.left.val==root.val)? left+1:0;
    let rightpath = (root.right&&root.right.val==root.val)? right+1:0;
    max = Math.max(max, leftpath+rightpath);
    return Math.max(leftpath,rightpath)
}
 depth(root);
 return max;
};
《----------------------------------------------------------------》
与之类似的还有129求路径的结点和，中等难度
var sumNumbers = function(root) {
    let sum = 0;
    let cur = 0;
    if(!root) return 0;
  const path = (root,cur)=>{
    cur = cur*10 + root.val;
    //叶子结点返回当前
   //根节点的值加左子树数字和加右子树数字和
    if(root.left) path(root.left, cur);
    if(root.right) path(root.right, cur);
    //叶子结点的时候和为cur
    if(!root.left&&!root.right) sum += cur;
}
path(root,0);
return sum;
};

Вопрос 11 - Поддерево 572

• Вопрос: Этот вопрос аналогичен решению вопроса 7-437, а также дважды рекурсивен, поэтому помещен здесь.

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
     3
    / \
   4   5
  / \
 1   2
给定的树 t：
   4 
  / \
 1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t：
   4
  / \
 1   2
返回 false。

LeetCode

• Анализ: аналогично предыдущему вопросу, двойная рекурсия. Первый уровень рекурсии заключается в обходе каждого узла, принятии каждого узла s в качестве корневого узла, а затем на втором уровне рекурсии оценивается, являются ли два дерева одинаковыми. То же самое в том, что дерево одинаково от корневого узла до конечного узла. Например, второй пример в заголовке возвращает false, потому что листовые узлы разные.
• код

var isSubtree = function(s, t) {
    if(!s) return false;
    //判断两棵树是否相同
    let judege = function(s, t) {
        if(!s&&!t) return true;
        if(!s||!t) return false;
        if(s.val != t.val){
         return false;
        }
       return judege(s.left,t.left)&&judege(s.right, t.right);
    }
    //三者只要一个成立即可
    return judege(s,t)|| isSubtree(s.left, t)|| isSubtree(s.right, t)
};

Обход бинарного дерева

Вопрос 12. Нерекурсивная реализация обхода бинарного дерева в прямом порядке 144

• тема

给定一个二叉树，返回它的 前序 遍历。
 示例:
输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

: LeetCode

• Анализ: предварительный обход, обход корневого узла, затем обход левого поддерева, а затем обход правого поддерева. Давайте напишем здесь итеративный алгоритм, то есть используем стек для нерекурсивной реализации обхода бинарного дерева.
• отвечать

var preorderTraversal = function(root) {
    let result = [];
    if(!root) return result;
    //递归
    // const helper = (root) => {
    //     if(root) result.push(root.val);
    //     if(root.left) helper(root.left);
    //     if(root.right) helper(root.right);
    // }
    // helper(root);
    // return result;
    //迭代
    let stack = [root];
    while(stack.length!=0){
        let node = stack.pop();
        result.push(node.val);
        if(node.right) stack.push(node.right);
        if(node.left) stack.push(node.left);
    }
    return result;
};

Вопрос 13 - Нерекурсивная реализация последующего обхода бинарного дерева 145(жесткий)

• тема

给定一个二叉树，返回它的 后序 遍历
示例:
输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [3,2,1]

LeetCode

• Синтаксический анализ: аналогично описанному выше методу, вы можете рекурсивно проходить по порядку, а затем выводить в обратном порядке. Вы также можете итерировать и обновлять верхний элемент стека каждый раз, чтобы получить результат обхода предварительного порядка, а затем вывести в обратном порядке. Стоит отметить, что обход по порядку左孩子，右孩子，根结点，. Тогда предзаказ根节点，右孩子，左孩子вместо根节点，左孩子，右孩子
• код

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    //先序遍历逆序后就是后序遍历
     let result = [];
    if(!root) return result;
    // const helper = (root) => {
    //     if(root) result.push(root.val);
    //     if(root.right) helper(root.right);
    //     if(root.left) helper(root.left);
    // }
    // helper(root);
    // return result.reverse();
    let stack = [root];
    while(stack.length){
        let len = stack.length;
        while(len--){
            let node = stack.pop();
            result.push(node.val)
            if(node.left) stack.push(node.left);
            if(node.right) stack.push(node.right);
        }
    }
    return result.reverse();
};

Вопрос 14. Нерекурсивная реализация обхода бинарных деревьев по порядку 94 (умеренно)

• тема

给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

LeetCode

• Мысль: хотя эта тема имеет умеренную сложность, я думаю, что обход по порядку — самая сложная из трех. Сначала заталкиваем все левое поддерево корневого узла в стек через указатель узла, вынимаем верхний элемент стека и сохраняем значение узла в результат. Если выбранный верхний элемент стека имеет правое поддерево, пусть правое поддерево помещается в стек по порядку, а затем извлекается верхний элемент стека. Два более сложных для понимания момента закомментированы в коде
• код

var inorderTraversal = function(root) {
    let result = [];
    if(!root) return result;
    let stack = [root];
    let node = root.left;
    //添加node存在是处理根节点没有左子树的情况。没有左子树stack.length=0的时候海曙要将右子树入栈
    while(stack.length || node) {
       while(node) {
           //结点入栈
           stack.push(node);
           node = node.left
       }
        node = stack.pop();
        result.push(node.val);
        node = node.right;//node.right存在就将node.right这个树的左节点入栈
    }
    return result;
};

Вопрос 15. Симметрия деревьев 101

• тема

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3
进阶：你可以运用递归和迭代两种方法解决这个问题吗？

LeetCode

• Разбор: Во-первых, реализуем рекурсивно, если дерево симметрично, то левое поддерево и правое поддерево симметричны, а правое поддерево и левое поддерево симметричны.镜像对称=左子树的第一个孩子的value和右子树第一个孩子的value相等+左左子树和右右子树对称+右右子树和左左子树对称
• код

//递归
var isSymmetric = function(root) {
    if(!root) return true;
    let same = function(root1, root2) {
        //遍历到最后还没有false并且结点空
        if(!root1&&!root2) return true;
        //任意一个是空或者两个结点的value不等。
        if(!root1||!root2||root1.val != root2.val) return false;
        return same(root1.left,root2.right)&&same(root1.right, root2.left);
    }
    return same(root.left,root.right);
};

Конечно, есть и итерационный метод с использованием очередей, каждый раз берущий два элемента в начале очереди, а затем сравнивающий, равны ли значения. Если два узла пусты для следующего цикла, если один из них пуст или два значения не равны, это будет ложью, потому что следует обратить внимание на порядок четырех узлов в очереди.

//非递归
var isSymmetric = function(root) {
    //非递归实现
    let quene = [];
    if(root.left.val!=root.right.val) return false;
     quene.push(root.left);
     quene.push(root.right);
    while(quene.length){
        let left = quene.shift();
        let right = quene.shift();
        // if(left.left!=right.right||left.right!=right.left) return false;逻辑错误
        if(!left&&!right) continue;
        if(!left||!right || left.val != right.val) return false;
        //入队列
        if(left.left) quene.push(left.left);
        if(right.right) quene.push(right.right);
        if(left.right) quene.push(left.right);
        if(right.left) quene.push(right.left);
    }
    return true;
};

Вопрос 16 - Подсчитайте сумму левого листового узла 404

• тема

计算给定二叉树的所有左叶子之和。
示例：
    3
   / \
  9  20
    /  \
   15   7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

LeetCode

• Анализ: рекурсивная реализация, если левое поддерево является конечным узлом, то возвращается значение левого поддерева плюс результат обработки правого поддерева. Если левое поддерево не является конечным узлом, возвращается результат обработки левого поддерева и правого поддерева.Существует три условия для определения того, является ли левое поддерево конечным узлом, одно из которых состоит в том, что узел существует, а другое - что у узла нет левого дочернего элемента, в-третьих, что у узла нет правого дочернего элемента.
• код

var sumOfLeftLeaves = function(root) {
    if(root==null) return 0;
    if(root.left&&!root.left.left&&!root.left.right) return root.left.val+sumOfLeftLeaves(root.right);
    else return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
};

Вопрос 17 - Интервальный обход (Семейное ограбление 2 - Хороший вопрос) 337

• тема

聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

LeetCode

• Анализ: здесь для обхода дерева используется рекурсивный метод, а динамическое программирование помещено в столбец динамического программирования для объяснения. Этот вопрос можно понимать как максимальную сумму значений интервальных узлов в бинарном дереве. Таким образом, есть два случая, первый использует корень как текущее максимальное значение, тогда лево и право корня не могут быть учтены. Общий максимумroot+root.left.left+root.left.right+root.right.left+root.right.rightузел и.

  Второй случай заключается в том, что корень не включен, а сумма узлов root.left+root.right принимается за максимальное значение. Окончательное максимальное значение должно быть максимальным значением первого и второго типов. Выходом для рекурсии является возврат 0, когда узел не существует.

• отвечать:

var rob = function(root) {
    if(!root) return 0;
    let result1 =root.val ;
    //第一种
    if(root.left)result1 += rob(root.left.left) + rob(root.left.right);
    if(root.right) result1 +=rob(root.right.left)+ rob(root.right.right);
    //第二种
    let result2 = rob(root.left) + rob(root.right);
    return Math.max(result1, result2);
};

• Дополнение: Я не придумал эту тему в начале рекурсии.Почувствовал лень.Отдохнув,ловил себя на этой мысли.Пройти текущий узел и найти максимальное значение текущих двух ситуаций , Текущее максимальное значение также две ситуации. Найдите их максимальное значение. Окончательный результат является результатом сравнения между результатом1 и результатом2. результат2 результатresult2 = rob(root.left) + rob(root.right);Результат rob(root.left) является результатом сравнения двух вариантов root.left в качестве корневого узла. rob(root.right) — это результат сравнения двух результатов root.right в качестве корневого узла.

Задача 18. Найдите второй наименьший узел в бинарном дереве 671

• тема

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入: 
    2
   / \
  2   5
     / \
    5   7
输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。
示例 2:
输入: 
    2
   / \
  2   2
输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

LeetCode

• Идея: я начал думать, что второе наименьшее значение должно быть среди первых левых и правых детей корневого узла, поэтому есть неправильное решение. Однако из сообщения об ошибке известно, что второе наименьшее значение может появиться в любой позиции поддерева (когда значение дочернего узла совпадает со значением корневого узла), поэтому требуется рекурсия.
  • Второе наименьшее значение не может быть корневым узлом, поэтому найдите меньшее из левого и правого поддеревьев как второе наименьшее значение.
  • Когда left.val==root.val, найдите второе наименьшее значение левого поддерева как значение left. Точно так же, когда right.val==root.val, найдите второе наименьшее значение правого поддерева как правильное значение.
  • Затем сравните большую справа и слева.

• неправильная идея

//错误的思路：考虑不周部分测试用例通过，比如[1,1,3,11,34,3,1,1,1,3,8,4,8,3,3,1,2]这棵树就不成立。
//有0或2个叶子结点。
var findSecondMinimumValue = function(root) {
    //没有结点
    if(!root) return -1;
    //只有一个根节点
    if(!root.left&&!root.right) return -1;
    //有一个叶子结点
    if(!root.left||!root.right) return (root.left.val||root.right.val)> root.val?(root.left.val||root.right.val):-1;
    //有两个叶子结点找到两个叶子结点的小者
    if(root.left.val ==root.val&&root.right.val == root.val) return -1;
    if(root.left.val==root.val) return root.right.val;
    if(root.right.val == root.val) return root.left.val;
    return Math.min(root.left.val,root.right.val)
};

• правильное решение

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
//有0或2个叶子结点。
var findSecondMinimumValue = function(root) {
    //没有结点
    if(!root) return -1;
    //只有一个根节点
    if(!root.left&&!root.right) return -1;
    //有两个叶子结点
    let left = root.left.val;
    let right = root.right.val;
    if(left == root.val) left = findSecondMinimumValue(root.left);
    if(right == root.val) right = findSecondMinimumValue(root.right);
    //左右子树都存在
    if(left != -1 && right !=- 1) return Math.min(left, right);
    // 只存在左子树
    if(left != -1) return left;
    //只存在右子树
    return right;
};

Вопрос 19. Среднее значение узлов на каждом уровне дерева равно 637.

• тема:

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
    3
   / \
  9  20
    /  \
   15   7
输出: [3, 14.5, 11]
解释:第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

LeetCode

• Анализ: обход порядка слоев с использованием очереди. Двухслойный цикл, цикл первого слоя представляет собой текущий слой, а второй цикл представляет собой дерево узлов этого слоя. Узлы первого слоя ставятся в очередь и вычисляется среднее значение. Затем узлы второго слоя ставятся в очередь и вычисляется среднее значение. пока очередь не опустеет.
• отвечать

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 层次遍历（同第10题的最小路径111-思路2）
 */
var averageOfLevels = function(root) {
 let quene = [root];
 let result = [];
 while(quene.length){
     let size = quene.length;let sum = 0;let node =null;
     for(let i = 0; i< size; i++){
        node= quene.shift();
        sum+=node.val;
        if(node.left) quene.push(node.left);
        if(node.right) quene.push(node.right);
     }
     result.push(sum/size);
 }
 return result;
};

• Решение 2. Используйте обход DFS для достижения: обхода предварительного порядка, записи глубины каждый раз, когда вы проходите, построения двумерного массива arr[i][j], i представляет текущую глубину, j представляет значение узла текущего глубина. Наконец, метод сокращения используется для получения суммы каждого элемента двумерного массива, а среднее значение получается методом карты.

var averageOfLevels = function(root) {
let arr = [];
if(!root) return arr;
const Deepfs = (root, level) => {
    (arr[level]||(arr[level]=[])).push(root.val);
    if(root.left)Deepfs(root.left, level+1);
    if(root.right)Deepfs(root.right, level+1);
}
Deepfs(root, 0);
 return arr.map(item => { return item.reduce((pre, cur)=> pre+cur)/item.length});
};

Вопрос 20 - Получить узел в левом нижнем углу 513

• тема

给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
    2
   / \
  1   3
输出:
1

• Анализ: Аналогично предыдущей теме. Дерево обходим в глубину или в ширину. Обход в ширину сначала ставит в очередь правое поддерево, а затем левое поддерево. Последний элемент, взятый из очереди, является самым левым дочерним узлом. Здесь я в основном хочу поговорить о обходе в глубину.Очень умный способ мышления заключается в том, что даже если глубина дерева обновляется, использовать результат для записи текущего значения самого глубокого узла является значением самого левого узла и возвращать результат, когда дерево пройдено.
• код

var findBottomLeftValue = function(root) {
    let maxLevel = -1;
    let result = root.val
     const DFS = (root, level) => {
         if(level>maxLevel) {
             maxLevel = level;
             result = root.val;
         }
         if(root.left) DFS(root.left, level+1);
         if(root.right) DFS(root.right, level+1);
     }
     DFS(root, 0);
     return result;
};

бинарное дерево поиска

Вопрос 21. Обрезка двоичного дерева поиска 669

• тема

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 2:
输入: 
    3
   / \
  0   4
   \
    2
   /
  1
  L = 1
  R = 3
输出: 
      3
     / 
   2   
  /
 1

LeetCode

• Анализ: в этой теме сначала нужно узнать, что такое двоичный поисковый номер. Размер корневого узла двоичного поискового числа равен среднему значению, то есть левая часть корневого узла меньше корневого узла, а правая часть корневого узла больше корневого узла. обрезки = результат обрезки левого поддерева и результат обрезки правого поддерева. Результат сокращения правого поддерева является результатом сокращения правого и левого поддерева плюс сокращения правого и левого поддерева.
• код

//L和R就是左右边界
var trimBST = function(root, L, R) {
    if(!root) return null;
    if(root.val> R){
        return trimBST(root.left, L, R);
    }else if(root.val< L){
        return trimBST(root.right, L, R);
    }
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;
};

Вопрос 22. Нахождение k-го элемента бинарного дерева поиска 230

• тема

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

LeetCode

• Анализ: характеристика числа двоичного поиска заключается в том, что обход по порядку упорядочен, поэтому после обхода по порядку двоичного дерева поиска k-1-й результат является k-м наименьшим значением двоичного дерева поиска.

• код

var kthSmallest = function(root, k) {
    let result=[];
    if(!root) return ; 
    const helper = (root) => {
        if(root.left) helper(root.left);
        result.push(root.val);
        if(root.right) helper(root.right);
    }
    helper(root);
    return result[k-1];
};

Вопрос 23 - Прибавьте значение каждого узла бинарного дерева поиска к значению узла большего, чем он 538

• тема

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和
例如：
输入: 原始二叉搜索树:
              5
            /   \
           2     13
输出: 转换为累加树:
             18
            /   \
          20     13

LeetCode

• Анализ: Прежде всего, вы должны пройти по дереву, как пройти. Чтобы узнать максимальное значение. Мы можем пройти по порядку.右孩子，根结点，左孩子пройти по порядку. При обходе текущее значение узла записывается и представляется в виде суммы. Значение узла следующего корня узла является суммой его собственного значения и суммы.

Пример на Val из узла 8 составляет 8 + 0, SUM = Val = 8; затем перейти к узлу. 7 - SOUT 7 + SUM = 15, SUM = VAL = 15 и 4 - это тот же узел.

• код

if(!root) return root;
let sum = 0;
//遍历函数
const helper = (root)=>{
    if(!root) return;
    helper(root.right);
    root.val+=sum;
    sum = root.val;
    helper(root.left);
}
helper(root);
return root
};

Вопрос 24. Ближайший общий предок бинарного дерева поиска 235

• тема

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

LeetCode

• Идея: это может быть рекурсивно или итеративно. Когда значение pq меньше значения корневого узла, он ищется в левом поддереве, а если значение pq больше значения корневого узла, он ищется в правом поддереве. Здесь следует отметить, что p и q — это два узла, а не значения узлов, при сравнении используйте p.val.
• Код (нерекурсивный итерационный метод)

var lowestCommonAncestor = function(root, p, q) {
   //与上面逻辑类似，但是是不断迭代更新root
    while(root){
        if(root.val > q.val && root.val > p.val) root = root.left;
        else if(root.val < q.val && root.val < p.val) root = root.right;
        else{
            return root;
        }
    }
};

Вопрос 25. Построение двоичного дерева поиска из упорядоченного массива 108

• тема

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5

LeetCode

• Анализ: Эта задача требует построения хорошо сбалансированного бинарного дерева, то есть среднего значения упорядоченного массива в качестве корневого узла. Затем разделите массив на две половины, чтобы построить сбалансированное по высоте левое двоичное дерево и правое суббинарное дерево со сбалансированной высотой соответственно. Длина массива нечетная и берется среднее значение, а длина массива четная и одно из двух средних значений.
• код

var sortedArrayToBST = function(nums) {
    if(nums.length==0) return null;
        const helper = (nums) => {
        if(nums.length==0) return null;
        let len = nums.length;
        let i = Math.floor((len)/2);
        let root = new TreeNode(nums[i]);
        root.left = helper(nums.slice(0, i));
        root.right = helper(nums.slice(i + 1));
        return root;
    }
    return helper(nums);
};

Вопрос 26. Построение двоичного дерева поиска из упорядоченного связанного списка 109

• тема

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5

LeetCode

• Идея: Построение бинарного дерева на основе упорядоченного связанного списка не так гибко, как упорядоченный массив, потому что связанный список нельзя быстро найти по индексам, как массив. Таким образом, мы передаем быстрый и медленный указатель, быстрый указатель перемещается вперед на два узла за раз, а медленный указатель перемещается на один узел за раз. Когда быстрый указатель является последним узлом (длина связанного списка нечетна), быстрый указатель является предпоследним узлом (длина связанного списка четна), а медленный указатель является средней позицией. Для левой стороны таким же образом найдите среднее значение левого связанного списка и таким же образом найдите среднее значение правого связанного списка.
• Я не знаю, есть ли у друзей тот же вопрос, что и у меня,root.right = helper(slow.next, tail);//tail不能写成nullПочему хвост прямо не записывается как нуль. В конце концов, хвостовой узел справа нулевой. После некоторого анализа хвостовой узел связанного списка справа от среднего значения, найденного в первый раз, действительно является хвостом, но впервые хвостовой узел связанного списка слева от среднего значения является позицией указывает медленно. Поэтому писать ноль неправильно.
• код

/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    if(!head) return null;
    const helper = (head, tail)=> {
        if(head == tail) return null;
        let fast = head, slow = head;
        //对应链表是偶数和奇数两种情况
        while(fast!=tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        let  root = new TreeNode(slow.val);
        root.left = helper(head, slow);
        root.right = helper(slow.next, tail);//tail不能写成null
        return root;
    }
    return helper(head, null);
};

Вопрос 27. Найдите два узла в двоичном дереве поиска, сумма которых равна заданному значению 653.

• тема

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入: 
    5
   / \
  3   6
 / \   \
2   4   7
Target = 9
输出: True

LeetCode

• Анализ: две идеи, сначала сбалансированные значения узлов дерева в упорядоченный массив, а затем с помощью указателей скорости. Вторая идея заключается в обходе каждого узла дерева с каждым значением узла записи набора обхода. Если результат текущей точки значение k существует Установить структуру соединения. Затем, что есть два узла. Если узлы не были пройдены, возвращается false.
• код

var findTarget = function(root, k) {
    if(!root) return false;
    let s = new Set();
    const helper  = (root, k, s) => {
        if(!root) return false;
        if(s.has(k-root.val)) return true;
        s.add(root.val);        
        return helper(root.left, k, s) || helper(root.right, k,s);
    }
   return helper(root, k, s)
};

Вопрос 28 - Найдите минимальное абсолютное значение двух узлов в бинарном дереве поиска 530

• тема

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：
   1
    \
     3
    /
   2
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

LeetCode

• Анализ: Минимальное значение разности абсолютных значений должно появиться в любых двух соседних узлах при неупорядоченном обходе бинарного дерева поиска. Поэтому обход бинарного дерева выполняется по порядку, и в качестве минимального значения разности используется значение текущего узла за вычетом значения предыдущего узла. Пройдите каждый узел с новой минимальной мин.
• код

var getMinimumDifference = function(root) {
    // if(!root) return Number.MAX_VALUE;
    let min = Number.MAX_VALUE;
    let prenode = null;
    const helper = (root) => {
        if(root.left) helper(root.left);
        if(prenode) min = Math.min(min, root.val - prenode.val);
        prenode = root;
        if(root.right) helper(root.right);
    }
    helper(root);
    return min;
};

Вопрос 29 - Найдите наиболее часто встречающееся значение в бинарном дереве поиска 501

• Вопрос: Верните узел с наибольшим количеством вхождений в двоичном дереве поиска. Предположим, что бинарное дерево поиска определено так, что левое поддерево меньше или равно корневому узлу, а правое поддерево больше или равно корневому узлу.
• Анализ: Результат последовательного обхода упорядочивается. невозможный[1,2,2,3,4,2,2,5]Такая последовательность, следовательно, проходит через каждый узел. Если значение текущего узла равно значению предыдущего узла. Тогда количество вхождений count++, если не равно новое значение, пусть count=1. Затем сравните размер через количество и макс. max — это количество раз, когда узел текущего режима появляется. Если count больше max, будет найден новый результат. Если они равны, будет найден один и тот же результат. Если count меньше max, продолжайте обход следующего узла. Сделайте то же самое для следующего узла, пока узел не будет пройден.
• код

var findMode = function(root) {
    // 1.中序遍历当前值和上一个值比较是否相同。相同则加1，不相同count就是1表示当前是一个新元素
    //没比较一次就要看是否更新最大值
    //如果count>max就更新最大值，清空结果数组，添加新的数据到结果数组
    //如果count= max就说明当前出新次数和之前出现的次数一样多，直接添加新数据到结果数组
    let prenode = null;
    let count = 1;
    let max = 1; let res = [];
    const helper = (root) => {
        if(!root) return;
        helper(root.left);
        if(prenode) {
            if(root.val==prenode.val) count++; 
            else count=1;
        }
        if(count > max){
            max = count;
            res = [];
            res.push(root.val);
        }else if(count == max) res.push(root.val);
        prenode = root;
        helper(root.right);
    }
    helper(root);
    return res;
};

общий предок

Помните общего предка бинарного дерева поиска в вопросе 24, мы реализовали итеративно выше, здесь мы используем рекурсию для реализации общего предка обычного бинарного дерева

Вопрос 30. Последний общий предок бинарных деревьев 236

• Вопрос: Учитывая бинарное дерево, найдите ближайшего общего предка двух указанных узлов в дереве.литкод вопрос 236
• Анализ: посмотрите, равно ли текущее значение узла значению узла любого из q и p. Если он равен, то общий предок является текущим узлом. Если нет, посмотреть, существуют ли p и q в левом поддереве и правом поддереве. Логика суждения находится в комментариях кода. Кроме того, согласно заголовку, мы можем знать, что не будет никакой разницы между p и q Это относится к случаю узла бинарного дерева.
• код

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(!root || root.val == p.val || root.val == q.val) return root;
    let left = lowestCommonAncestor(root.left, p, q);
    let right = lowestCommonAncestor(root.right, p, q);
    //如果left不存在p或q就返回right的结果。如果left存在，right不存在就返回left结果。如果left和right都存在就返回根节点
    if(left == null) return right;
    else if(right == null) return left;
    return root;
};

префиксное дерево

Вопрос 31 - Реализация шины 208 (середина)

• тема

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

LeetCode

• Анализ: дерево префиксов также называют деревом словарей. Также в начале статьи есть описание

❝

Также известное как дерево поиска слов, дерево Trie, представляет собой древовидную структуру, вариант хеш-дерева. Типичным приложением является подсчет, сортировка и сохранение большого количества строк (но не только строк), поэтому поисковые системы часто используют его для статистики частотности текстовых слов. Его преимущества: использование общего префикса строк для сокращения времени запроса, минимизация ненужных сравнений строк, эффективность запросов выше, чем у хеш-деревьев. ----"Энциклопедия Байду"

❞

• Анализ: Это может быть самый сложный вопрос среди этих вопросов, потому что нужно написать три функции.На самом деле, можно написать самую важную функцию вставки, поэтому следующие две функции одинаковы. Буду писать комментарии в коде, если есть место, обязательно звоните мне в зону комментариев.

• код

• js-реализация

//定义trie树的结构
function Trie(val) {
//每一个结点都最多有26个孩子，用数组存
this.next  = new Array(26);
//是否是叶子结点，默认false
this.isEnd = false;
//结点值，是一个字符类型
this.val = val;
};
/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let len = word.length;
    //node表示当前的trie结点
    let node = this;
    for(let i = 0; i< len; i++) {
    //word[i]是一个字符串类型，charCodeAt方法将他转换成Ascii码
    //比如字符b的ascii码是98，那么n=1；
        let n = word[i].charCodeAt()-97;
        //如果node孩子结点中已经存在这个字符就让当前的trie等于这个结点的孩子trie
        //如果node孩子节点数组中不存在我们就构造这样的一个trie
        if(node.next[n] && node.next[n].val==word[i]){
            node = node.next[n]
        }else {
            node.next[n] = new Trie(word[i]);
            node= node.next[n];
        }
    }
    //构造完毕让最后一个trie的isEnd属性标记为true，表示最后一个结点
    node.isEnd = true;
};
Trie.prototype.search = function(word) {
    if(!word) return false;
    let len = word.length;
    let node = this;
    let result = true;
    for(let i = 0; i < len; i++) {
        let n = word[i].charCodeAt()-97;
        if(node.next[n]&&node.next[n].val==word[i]) {
            node = node.next[n];  
        }
        else {
           result = false; 
           break;
        }
    }
    //search的时候如果次数result是true还要判断此时node是否是前缀树的叶子结点，如果不是还是会返回false
    if(result) result = node.isEnd;
    return result;
};
//search明白了这个函数也就明白了
Trie.prototype.startsWith = function(prefix) {
    let len = prefix.length;
    let node = this;
    let result = true;
    for(let i = 0; i < len; i++) {
        let n = prefix[i].charCodeAt()-97;
        if(node.next[n]) {
            node = node.next[n];  
        }
        else {
           result = false; 
           break;
        }
    }
    return result;
};

• Java-реализация

class Trie {
    // 当前节点的值
    public char value;
    //a-z有26个字母，需要访问时由于a的ASCII码为97，所以所有字母访问的对应下标皆为 字母的ASCII码-97
    public Trie[] children=new Trie[26];
    // 标识此节点是否为某个单词的结束节点
    public boolean endAsWord=false;
    public Trie() {
    }
    public void insert(String word) {
        if(word!=null){
            //分解成字符数组
            char[] charArr=word.toCharArray();
            //模拟指针操作,记录当前访问到的树的节点
            Trie currentNode=this;
            for(int i=0;i<charArr.length;i++){
                char currentChar=charArr[i];
                //根据字符获取对应的子节点
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{//不存在则创建一个新的叶子节点,并指向当前的叶子节点
                    node=new Trie();
                    node.value=currentChar;
                    currentNode.children[currentChar-97]=node;
                    currentNode=node;
                }
            }
            //这个标识很重要，将最后叶子结点标记true在后面的serach中有用
            currentNode.endAsWord=true;
        }
    }
    public boolean search(String word) {
        boolean result=true;
        if(word!=null && !word.trim().equals("")){
            char[] prefixChar=word.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                   currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
            if(result){
                result=currentNode.endAsWord;
            }
        }
        return result;
    }
    public boolean startsWith(String prefix) {
        boolean result=true;
        if(prefix!=null && !prefix.trim().equals("")){
            char[] prefixChar=prefix.toCharArray();
            Trie currentNode=this;
            for(int i=0;i<prefixChar.length;i++){
                char currentChar=prefixChar[i];
                Trie node=currentNode.children[currentChar-97];
                if(node!=null && node.value==currentChar){//判断节点是否存在
                    currentNode=node;
                }else{
                    result=false;
                    break;
                }
            }
        }
        return result;
    }
}

Дополнительно: хвостовая рекурсия

Всем известно, что рекурсия склонна к переполнению стека, потому что функция не уничтожается и не помещается в стек после помещения в стек.Число рекурсии определяет пространство, которое вы открываете в стеке, поэтому, если количество рекурсии слишком много , легко переполнить стек.

Отсюда и хвостовая рекурсия. Итак, что такое хвостовая рекурсия, хвостовая рекурсия происходит от хвостового вызова, хвостовой вызов подробно описан в «Введении в стандарт ES6», то есть функция B возвращается хвостом функции A, а функция B не использует функцию A, поскольку это последний шаг функции A, стек выполнения A уничтожается при выполнении функции B. Поскольку местоположение вызова и внутренние переменные больше не используются, вы можете напрямую использовать стек вызовов внутренней функции для замены внешней функции.

Вот статья о хвостовой рекурсии и временной сложности, которую, я думаю, вы хорошо поняли и поделились с вами.хвостовая рекурсия

наконец

Наконец, позвольте мне рассказать о моем личном отношении к алгоритму.

Алгоритм действительно сложно в начале, но когда вы начинаете позже, вы найдете это с мышлением, вы найдете алгоритм, чтобы быть очень интересным, особенно когда космическая сложность и сложность времени ударили на 100%. Очень счастлив.

В начале я вообще не понимал рекурсивного мышления, мог только запихнуть человеческий мозг в стек, писать код вручную и расписывать каждый шаг. В итоге прошел один день, а иногда могу написать, что кружится голова, я мразь 🤷‍♂️

Есть еще две вещи, которые я хочу сказать

• Обход дерева и пять случаев, все вышеперечисленные темы в конечном итоге обход дерева анализа.
• Внимательно пишите алгоритмические вопросы , нужно ли алгоритмам терпение и настойчивость

Если вы не практиковали ответы на приведенные выше вопросы, потратьте много времени на их практику. Если вы сами сможете написать эти вопросы, я думаю, в будущем алгоритм будет работать все быстрее и быстрее (старший брат, пожалуйста, в обход 👀👍)

Если вы ничего не понимаете в теме в нем, просто прокомментируйте и позвоните мне, если вы не избавитесь от того, чтобы называть меня отморозком, это нормально~

Напоследок хочу поздравить с запоздалым 1 мая Международным днем ​​труда и пожелать всем насыщенного праздника💕🐱‍🏍~

В этой статье используетсяmdniceнабор текста

Приложение: Раньше это выглядело так, как будто человеческий мозг запихнули в стек для рекурсии 🤷‍♀️...️