Основы двоичного дерева
Я выполняю задачу leet code, которая называется бинарным наклоном. Ссылка на вопрос здесь: https://leetcode.com/problems/binary-tree-tilt/description/
Я застрял в вопросе, поэтому взглянул на решение и надеялся, что кто-то сможет интерпретировать части приведенного ниже решения для меня:
public class Solution {
int result = 0;
public int findTilt(TreeNode root) {
postOrder(root);
return result;
}
private int postOrder(TreeNode root) {
if (root == null) return 0;
int left = postOrder(root.left);
int right = postOrder(root.right);
result += Math.abs(left - right);
return left + right + root.val;
}
}
целые числа left и right устанавливаются в значение каждый раз, когда происходит рекурсия. Я не понимаю, откуда взялось это значение, поскольку я думал, что нужно будет использовать метод root.val. Можете ли вы объяснить это в терминах непрофессионала?
Когда метод postOrder возвращает left + right + rootval, куда возвращается метод? Как это используется с рекурсивным методом?
Ответы 1
Я думаю, что вас сбивает с толку то, что вычисление суммы левого и правого поддерева и вычисление наклона для каждого узла объединены в одном методе. Итак, я упростил код, который вы предоставили, чтобы его было легче понять, и добавил к нему комментарии. Хотя этот способ намного менее эффективен, потому что вы вычисляете сумму для левого и правого поддерева каждого узла (при каждом вызове calculateTilt), но он все равно принимается leetcode:
public class Solution {
int result = 0; //instance variable to accumulate result(tilt) for all nodes in the tree
public int findTilt(TreeNode root) {
calculateTilt(root);
return result;
}
private void calculateTilt(TreeNode root) {
if (root == null)
return;
int left = findTreeSum(root.left); //find sum of all nodes values of the left subtree
int right = findTreeSum(root.right); //find sum of all nodes values of the right subtree
result += Math.abs(left - right); //add tilt of current node to the result
calculateTilt(root.left); //recursively calculate tilt for the left subtree
calculateTilt(root.right); //recursively calculate tilt for the right subtree
}
//method to find sum of all nodes values for the tree starting at root
private int findTreeSum(TreeNode root){
if (root == null)
return 0;
return findTreeSum(root.left) + findTreeSum(root.right) + root.val;
}
}
Надеюсь, это поможет!
Отлаживайте его или, что еще лучше, для понимания стека вызовов рекурсии отрисовки.