Часть этого замечательного узла взята из блога:
«九章 算法 笔记 3. 二叉树 与 分 治 算法 Binary Tree Divide Conquer
所有 内容 来自 于 www.jiuzhang.com 大纲 * 时间 复杂 度 训练 II * 二叉树 的 遍历 算法 Переход в двоичном дереве Preorder / Inorder / Postorder *
Контур
- Обход двоичного дерева DFS
- Preorder traverse Recicing
- Итеративный ход предварительного заказа
- Предзаказ разделяй и властвуй
2. Метод пересечения и разделяй и властвуй
- Максимальная глубина двоичного дерева
- Сбалансированное двоичное дерево
3. Максимальная сумма путей BT (корень- ›лист)
- Сумма максимального пути двоичного дерева II (корень- ›любой)
- Максимальная сумма пути двоичного дерева (любой- ›любой)
- Максимальная сумма пути двоичного дерева (любая - ›любая) с отрицательным значением
4. Дерево двоичного поиска
- Проверить дерево двоичного поиска
- Итератор двоичного дерева поиска
- Построить BST
- Найти элемент в BST
- Обрезка BST
- Сплит BST
5. Уровень двоичного дерева поиска по уровням
- Обход уровней бинарного дерева и порядка
Базовый
построить структуру TreeNode
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
1. Двоичное дерево обхода DFS
1.1 Предварительный заказ ：
vector<int> res;
void helper(TreeNode* root) {
if (!root) return;
res.push_back(root->val);
if (root->left) {
helper(root->left);
}
if (root->right) {
helper(root->right);
}
}
vector<int> preorderTraversal(TreeNode *root) {
if (!root) {
return res;
}
helper(root);
return res;
}
1.2 Divide and Conquer для реализации Preorder Traverse ：
Чтобы упростить понимание, у очереди есть цель, затем мы назначаем ее двум рабочим A и B, чтобы собрать результат из левого поддерева и правого поддерева, что мы получаем A = [2,4,5], B = [3]. Тогда окончательный результат = результат очереди + влево + вправо = [1,2,4,5,3].
vector<int>preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
//Divide, no need to check if the left exist or not
vector<int> left = preorderTraversal(root->left);
vector<int> right = preorderTraversal(root->right);
//Conquer
res.push_back(root->val);//current, left, right
res.insert(res.end(), left.begin(), left.end());
res.insert(res.end(), right.begin(), right.end());
return res;
}
1.3 Итеративный ход предварительного заказа ：
Таким образом, поскольку traverse - это метод DFS, который заставляет задуматься об использовании стека для сохранения результата. Примечание: поскольку стек - это FILO, если мы хотим сначала посетить левое поддерево, нам нужно сначала нажать правое поддерево. Эта итеративная реализация лучше, чем рекурсивная версия, потому что память, которую мы здесь используем, - это память кучи = размер памяти. В то время как для рекурсивной версии он использует стековую память = память обработки, поэтому легче исчерпать память.
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* tmp = s.top();
s.pop();
res.push_back(tmp->val);
// 这里注意：栈是先进后出，所以先push右子树
if (tmp->right) {
s.push(tmp->right);
}
if (tmp->left) {
s.push(tmp->left);
}
}
return res;
}
2. Траверс против "Разделяй и властвуй"
В этом разделе я буду включать примеры, чтобы проиллюстрировать, как использовать траверс и что это означает с «разделяй и властвуй».
2.1 Максимальная глубина двоичного дерева
https://www.lintcode.com/zh-cn/problem/maximum-depth-of-binary-tree/
Для двоичного дерева найдите максимальную глубину, которая определяется как наибольшее расстояние от корневого узла до листьев.
Пример
1
/ \
2 3
/ \
4 5Глубина этого двоичного дерева равна 3
Решение: обычный способ - использовать предварительный заказ, это DFS, поэтому нам нужно использовать глобальную переменную для сохранения максимальной высоты. Однако для этого намного проще использовать «разделяй и властвуй», мы получаем левую и правую высоту, затем мы используем max (left, right) +1, чтобы объединить результат. Кроме того, мы можем использовать BFS уровень за уровнем, чтобы пройти и получить максимальную высоту последнего уровня.
2.2 Сбалансированное двоичное дерево
Http://www.lintcode.com/zh-cn/problem/balanced-binary-tree/
Учитывая BT, нам нужно проверить, что это сбалансированное двоичное дерево. Определение сбалансированного двоичного дерева: если для каждого узла в данном BT разница глубины его левого поддерева и правого поддерева не будет больше единицы.
Пример
Учитывая BT A =
{3,9,20,#,#,15,7}, B ={3,#,20,15,7}
A) 3 B) 3
/ \ \
9 20 20
/ \ / \
15 7 15 7
A - сбалансированный BT ， B - нет
Нам просто нужно увидеть разницу в высоте левого поддерева и правого поддерева ›1: return False. return (True, 0) для базового случая.
2.3 Пути двоичного дерева
Для двоичного дерева вернуть все пути от корня к листу.
2.4 Минимальное поддерево
Для двоичного дерева найдите поддерево с минимальной суммой. Вернуть корень поддерева.
LintCode напечатает поддерево, корень которого является вашим возвращаемым узлом.
Решение: нам нужно получить значение всего дерева = помощник (слева) + помощник (справа) + текущий val. Гарантируется, что существует только одно поддерево с минимальной суммой, и данное двоичное дерево не является пустым деревом.
2.5 Максимальная сумма путей в BT
（1） максимальная сумма пути （корень- ›лист）
Пример:
Для следующих BT ：
1
/ \
2 3_5 _。 (Максимальный путь: 1 → 3)
Однако, если у нас отрицательное значение, это не сработает.
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0 #th
}
int left = maxPathSum2(root.left)
int right = maxPathSum2(root.right)
return root.val + Math.max(left, right) #at least root+one of the subtree
}
（2） максимальная сумма пути （корень- ›любой）
Максимальная сумма пути двоичного дерева II
Http://www.lintcode.com/zh-cn/problem/binary-tree-maximum-path-sum-ii/
Путь может быть от корня до любого узла, но он должен включать как минимум один узел, которым является корень.
Пример
Для следующих BT ：
1
/ \
2 3_7 _。 ( Максимальный путь 为 1 → 3)
Решение: этот немного отличается, для каждого узла мы можем вернуть сумму текущего узла + левого поддерева или текущего узла + правого поддерева, или мы просто возвращаем текущий узел, что означает, что путь здесь заканчивается.
За разделяй и властвуй ：
1.Рекурсивное конечное состояние ：, когда узел равен нулю
2.Divide ： разделить дерево на результат левого поддерева и правого поддерева
3. Завоевать ： объединить результат разделения.
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0;
}
//divide
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right);
//conquer
return root.val + Math.max(0, Math.max(left, right)); #if the max is negative, we get rid of them, use 0 instead.
}
（3） максимальная сумма пути （любой- ›любой）
2.5 Максимальная сумма пути двоичного дерева
124. Максимальная сумма пути двоичного дерева
Для BT найдите путь с максимальной суммой, этот путь может начинаться с любого узла и заканчиваться на любом узле.
Пример
Учитывая BT ：
1
/ \
2 3
Return6
Решение: разница по сравнению с предыдущим состоит в том, что результатом является не текущее значение плюс либо левое, либо правое, либо 0, это максимальная их сумма (за исключением текущего узла, левого и правого, мы добавляем только если он больше 0), что равно max (val, val + left, val + right, left + val + right, val). Также в этом процессе нам нужна глобальная переменная для сохранения максимального значения.
from sys import maxsize
class Solution:
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
maxv = -maxsize
def helper(root): #return max from current root to any node
nonlocal maxv
if not root:
return 0
tmp =root.val
left = helper(root.left)
right = helper(root.right)
if left>0:
tmp+=left
if right>0:
tmp+=right
maxv=max(maxv,tmp)
return max(0,max(left,right))+root.val
if not root:
return 0
helper(root)
return maxv
3. Обратитесь к результату обхода, чтобы построить дерево.
105. Построить двоичное дерево на основе обхода предзаказа и обхода без порядка
Учитывая предварительный и неупорядоченный обход дерева, построить двоичное дерево.
Примечание.
Вы можете предположить, что дубликаты не существуют в дереве.
Например, учитывая
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
Верните следующее двоичное дерево:
3
/ \
9 20
/ \
15 7
Решение: мы используем «разделяй и властвуй», сначала находим текущий узел как первый узел в предварительном порядке, а затем разрезаем порядок на две половины рядом с текущим узлом. По результату разделить предзаказ на две половины.
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
#first to decide the root
def helper(preorder,inorder):
if not preorder or not inorder:
return None
cur_val = preorder[0]
node = TreeNode(cur_val)
#divide: now cut the lists into two halfs
leftinorder,rightinorder = [],[]
bLeft=True
for e in inorder:
if e==cur_val:
bLeft=False #switch to the right side
continue
if bLeft:
leftinorder.append(e)
else:
rightinorder.append(e)
leftset, rightset = set(leftinorder),set(rightinorder)
leftpreorder, rightpreorder = [],[]
for e in preorder[1:]:
if e in leftset:
leftpreorder.append(e)
else:
rightpreorder.append(e)
#conquer
node.left=helper(leftpreorder, leftinorder)
node.right= helper(rightpreorder,rightinorder)
return node
return helper(preorder,inorder)
Однако с предыдущим кодом возникла проблема, поскольку тестовые примеры 203/203 были пройдены.
Статус: превышен предел памяти. Поэтому вместо передачи нового массива я использую index.
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
#first to decide the root
def helper(pre_l, pre_r,in_l, in_r): #[pre_l,pre_r)
if pre_l>=pre_r or in_l>=in_r:
return None
cur_val = preorder[pre_l]
node = TreeNode(cur_val)
#divide: now cut the lists into two halfs
leftinorder = set()
inorder_index = -1
for i in range(in_l, in_r):
if inorder[i]==cur_val:
inorder_index = i
break
leftinorder.add(inorder[i])
#when leftset is empty
new_pre_r=pre_l
for i in range(pre_l+1,pre_r):
if preorder[i] in leftinorder:
new_pre_r = i
else:
break
new_pre_r+=1
#conquer
node.left=helper(pre_l+1, new_pre_r, in_l, inorder_index)
node.right= helper(new_pre_r,pre_r, inorder_index+1, in_r)
return node
if not preorder or not inorder:
return None
return helper(0,len(preorder),0,len(inorder))
4. Временная сложность двоичного дерева
Если бы мы потратили O (n) на преобразование T (n) в 2T (n / 2)
T(n) = 2T(n/2) + O(n)
= 2 * 2T(n/4) + O(n) + O(n)
= nlogn (то же, что и сортировка слиянием)
If it is O(1)
T(n) = 2T(n/2) + O(1)
= 2 * 2T(n/4) + O(1) + O(1)
=n + (1 + 2 + 4 +…+ n)
≈n + 2n
≈O(n)
Дерево двоичного поиска (BST)
Дерево двоичного поиска: Вставить / Удалить / Найти / Проверить
Определение и особенности
F1: для BST все левое поддерево меньше текущего узла, а правое поддерево все больше текущего узла. Эта концепция полезна при обрезке BST, см. Пример 669. Обрезать двоичное дерево поиска.
- t.successor (x) - наименьший элемент в t, который строго больше x, null, если такого узла нет. Также называется последовательным преемником ,, который является следующим узлом в обходе двоичного дерева в порядке обхода. например, для узла 14, преемник (14) = 15 = min (14. right), преемник (15) = 18, где right не существует, тогда это родитель
definOrderSuccessor(root, n): # Step 1 of the above algorithm ifn.right isnotNone: returnminValue(n.right) # Step 2 of the above algorithm p =n.parent while( p isnotNone): ifn !=p.right :# if current node is the left node, then break break n =p p =p.parentreturnp
- t.predecessor (x) - самый большой элемент в t, который строго меньше x, null, если такого узла нет. например для узла 14 предшественник (14) = 12 = max (14. слева)
- LCA: наименьший общий предок определяется между двумя узлами v и w как наименьший узел в T, который имеет и v, и w в качестве потомков (где мы позволяем узлу быть потомком самого себя) ». например, если u = 5, w = 19, тогда мы сначала узел, когда мы рекурсивно посещаем дерево, которое находится внутри [u, w], тогда LCA равен 14.
- По порядку траверс можно использовать для сортировки. например 230. K-й наименьший элемент в BST
- Наименьшее и наибольшее значение
#recursive
def getSmallest(node):
if not node:
return None
if node.left:
return getSmallest(node.left)
return node
#iterative
def getSmallest(node):
while node:
node=node.left
return node
2. Общее решение
Для этого типа деревьев наиболее распространенный способ - сделать это рекурсивно с помощью BFS или DFS. Или иногда, если нам просто нужно найти элемент, мы можем использовать WHILE, чтобы делать это итеративно.
Шаги по решению проблемы:
Возьмите игрушечный пример: он должен быть достаточно большим, чтобы вмещать почти все ящики.
Если проблема простая и стандартная: выполните обход DFS (по порядку, по предварительному заказу, по завершении) (проще рекурсивно) или BFS (по уровням ) пройти (итеративно проще). Стандарт здесь означает, что мы можем получить ответ, просто просматривая элементы со стандартным определением.
Если проблема простая, но нестандартная: мы можем использовать цикл while для обхода поддерева, которое удовлетворяет условию и потенциально может привести нас к решение. Здесь получить игрушечный пример очень важно.
4. Если проблема сложнее и требует от нас манипулировать деревом, например обрезка, разделение с использованием рекурсивного метода, возвращающего узел. Сначала получите конечное условие, верните None или (None, None). Во-вторых, пройти по дереву в соответствии с требованием и вернуть узел. В-третьих, переставьте node, node.left, node.right и return
def RecursiveReturnNode(root):
#First
if not root:
return None
# second
if root.val is condition 1:
node =RecursiveReturnNode(node.left)
node.left manipulation
node.right manipulation
return node
if root.val is condition 2:
RecursiveReturnNode(node.left)
node.left manipulation
node.right manipulation
2.1 Создание BST
одно дерево из массива: 108. Преобразовать отсортированный массив в двоичное дерево поиска , всевозможное дерево: 96. Уникальные деревья двоичного поиска
108. Преобразовать отсортированный массив в двоичное дерево поиска
Учитывая массив, в котором элементы отсортированы в порядке возрастания, преобразуйте его в BST со сбалансированной высотой.
Для этой проблемы двоичное дерево со сбалансированной высотой определяется как двоичное дерево, в котором глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.
Пример:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Решение: используйте алгоритм двоичного поиска, условие остановки - когда l ›r.
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def generatebalancedBST(l,r):
if l>r:
return None
m = (l+r)//2
tree = TreeNode(nums[m])
tree.left = generatebalancedBST(l,m-1)
tree.right = generatebalancedBST(m+1,r)
return tree
return generatebalancedBST(0,len(nums)-1)
109. Преобразование отсортированного списка в двоичное дерево поиска , разница в том, что у нас есть связанный список, мы можем преобразовать связанный список в список чисел.
96. Уникальные деревья двоичного поиска
Учитывая n, сколько структурно уникальных BST (двоичных деревьев поиска), хранящих значения 1… n?
Например,
Если n = 3, всего существует 5 уникальных BST.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Решение: когда мы читаем сигнал, перечисляем его все, нам нужно использовать цикл for, чтобы представить каждый элемент как корень, и левая сторона - это левое дерево, правая сторона используется для правого дерева. Использовать DPS: мы сгенерировали все BST, которые используют i-й узел в качестве корневого.
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
def constructAllBST(start,end):
if start>end:
return [None]
#go through the start to end, and use the ith as root
rslt=[]
leftsubs,rightsubs=[],[]
for i in xrange(start,end+1):
leftsubs=constructAllBST(start,i-1)
rightsubs=constructAllBST(i+1,end)
for leftnode in leftsubs:
for rightnode in rightsubs:
node = TreeNode(i)
node.left=leftnode
node.right=rightnode
rslt.append(node)
return rslt
rslt= constructAllBST(1,n)
return len(rslt)
Если нам нужна только длина, немного лучшее решение, показанное ниже.
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
def constructAllBST(start,end):
if start>end:
return 1
#go through the start to end, and use the ith as root
count = 0
leftsubs,rightsubs=[],[]
for i in xrange(start,end+1):
leftsubs=constructAllBST(start,i-1)
rightsubs=constructAllBST(i+1,end)
count+=leftsubs*rightsubs
return count
rslt= constructAllBST(1,n)
return rslt
Однако тест по-прежнему не проходит, попробуйте восходящее итеративное решение с запоминанием: T (start, end) = T (start, i-1) * T (i + 1, end) T (j, i) = T (j, i-1) * T (i + 1, i). Как это объяснить?
def numTrees1(self, n):
res = [0] * (n+1)
res[0] = 1
for i in xrange(1, n+1): #when i=2, j=[0,1] res[2] = res[0]*res[2-1-0] + res[1]*res[2-1-1]
for j in xrange(i): #i [1,n], j =[0,i), the case if for one node,
res[i] += res[j] * res[i-1-j]
return res[n]Используя математику:
# Catalan Number (2n)!/((n+1)!*n!)
def numTrees(self, n):
return math.factorial(2*n)/(math.factorial(n)*math.factorial(n+1))2.2 Найдите определенный элемент дерева:
преемник или предшественник: 285. Inorder Successor в BST, 235. Самый низкий общий предок двоичного дерева поиска
285. Преемник в BST
Во-первых, мы можем следовать определению, использовать обход по порядку, чтобы получить список всех узлов, и мы ищем узел p и возвращаем его следующий в lst.
#takes 236 ms
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
lst = []
def inorderTravel(node):
if not node:
return None
inorderTravel(node.left)
lst.append(node)
inorderTravel(node.right)
inorderTravel(root)
for i in xrange(len(lst)):
if lst[i].val==p.val:
if i+1<len(lst):
return lst[i+1]
else:
return None
Однако определение берет O (N + N), также пространственная сложность O (N). Немного лучше вариант: когда мы ищем этот узел, преемником является последнее большее значение. Поэтому мы продолжаем записывать succ
#takes 108ms
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
#find min(p.right)
succ = None
while root:
if p.val < root.val: #node is bigger than p, go to left
succ = root #it might be the successor since its bigger
root = root.left
else: #node has the same value or smaller value than p, go to right
root = root.right
return succ
235. Самый низкий общий предок двоичного дерева поиска
Учитывая двоичное дерево поиска (BST), найдите наименьшего общего предка (LCA) двух заданных узлов в BST.
Согласно определению LCA в Википедии: Самый низкий общий предок определяется между двумя узлами v и w как самый низкий узел в T, который имеет и v, и w в качестве потомков (где мы позволяем узлу быть потомок самого себя) .
___________ / \ __1 / \ 2 3{3,9,20,#,#,15,7}_ __Return6_ / \ / \ 0 _4 7 9 / \ 3 5
Например, наименьшим общим предком (LCA) узлов 2 и 8 является 6. Другой пример - LCA узлов 2, а 4 это 2, поскольку узел может быть потомком самого себя в соответствии с определением LCA.
Решение: мы проходим по дереву, чтобы найти первый элемент в диапазоне.
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
s=min(p.val,q.val)
b=max(p.val,q.val)
def LCA(node):
if not node:
return None
if node.val>b:
return LCA(node.left)
if node.val<s:
return LCA(node.right)
return node
return LCA(root)
230. K-й наименьший элемент в BST
Решение: Здесь DFS-inorder-recursive; если мы используем python, то нам нужно использовать список как глобальную переменную
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
count = [k] #use list to function as global variable
num=[-1]
#inorder traversal
def inorder(node):
if node.left:
inorder(node.left)
count[0]-=1 #visit
if count[0]==0:
num[0]=node.val
return
if node.right:
inorder(node.right)
inorder(root)
return num[0]
Во-вторых: итеративная DFS
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
count = k
num=-1
#DFS iterative
#1: add all the left nodes
while root:
stack.append(root)
root=root.left
#visit stack, if node.right exist, then add in the stack
while stack:
node=stack.pop()
count-=1
if count==0:
return node.val
#check if the right exist
right=node.right
while right:
stack.append(right)
right=right.left #keep getting the successor
270. Ближайшее значение дерева двоичного поиска
Учитывая непустое двоичное дерево поиска и целевое значение, найдите в BST значение, наиболее близкое к целевому.
Примечание.
- Заданное целевое значение - это число с плавающей запятой.
- Гарантируется, что в BST будет только одно уникальное значение, наиболее близкое к цели.
from sys import maxint
class Solution:
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
mind= maxint #current smallest
rslt= -1
while root:
if root.val>target:
if root.val-target<mind:
mind = root.val-target
rslt=root.val
root=root.left
elif root.val<target:
if target-root.val<mind:
mind = target - root.val
rslt=root.val
root=root.right
else:
return root.val
return rslt
272. Ближайшее значение дерева двоичного поиска II
2.3 Обрезать дерево
может быть со значением в диапазоне: 669. Обрезать двоичное дерево поиска
669. Обрезать двоичное дерево поиска
Учитывая двоичное дерево поиска и нижнюю и верхнюю границы как L и R, обрежьте дерево так, чтобы все его элементы лежали в [L, R] (R ›= L). Возможно, вам потребуется изменить корень дерева, поэтому результат должен вернуть новый корень обрезанного двоичного дерева поиска.
Пример 1:
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
Решение: на основе F1, если значение текущего узла меньше, чем L, предположим, в 0, затем мы удаляем его левый дочерний элемент, node.left = None, затем мы проверяем его правый размер, переходим к node.right, мы возвращаем node = goto (node.right), если он находится в пределах диапазона, мы продолжаем проверять left, right и возвращаем текущий node
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
def trimUtil(node):
if not node:
return None
if node.val<L:
node.left=None #cut the left, the left subtree is definitly smaller than L
node =trimUtil(node.right) #node = node.right #check the right
return node
elif node.val>R:
node.right=None
node=trimUtil(node.left)
return node
else:
node.left=trimUtil(node.left)
node.right=trimUtil(node.right)
return node
return trimUtil(root)
Мутант состоит в том, чтобы разделить BST на два: один меньше или равен заданному значению, другой больше.
2.4 Разделить дерево
с определенным значением 776. Split BST
Учитывая дерево двоичного поиска (BST) с корневым узлом root и целевым значением V, разделите дерево на два поддерева, где одно поддерево имеет узлы, которые все меньше или равны целевому значению, в то время как другое поддерево имеет все узлы, которые являются больше целевого значения. Это не обязательно тот случай, когда дерево содержит узел со значением V.
Кроме того, большая часть структуры исходного дерева должна остаться. Формально, для любого дочернего элемента C с родительским элементом P в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел C все еще должен иметь родительский элемент P.
Вы должны вывести корневой TreeNode обоих поддеревьев после разделения в любом порядке.
Пример 1:
Input: root = [4,2,6,1,3,5,7], V = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
Explanation:
Note that root, output[0], and output[1] are TreeNode objects, not arrays.
The given tree [4,2,6,1,3,5,7] is represented by the following diagram:
4
/ \
2 6
/ \ / \
1 3 5 7
Решение: Кодировка очень похожа на обрезку.
class Solution(object):
def splitBST(self, root, V):
"""
:type root: TreeNode
:type V: int
:rtype: List[TreeNode]
"""
def splitUtil(node):
if not node:
return (None,None)
if node.val<=V:
sb1,sb2 = splitUtil(node.right) #the left subtree will satisfy the condition, split the right subtree
node.right=sb1 #Now set the right subtree with sb1 that
return (node, sb2)
else:
sb1, sb2=splitUtil(node.left) #the right subtree satisfy the condition, split the left subtree
node.left=sb2
return (sb1,node)
return list(splitUtil(root))
