Основы двоичного дерева - PullRequest
Новая
       76

Основы двоичного дерева

0 голосов
/ 19 сентября 2018

Я выполняю задание с кодом leet, которое называется Binary tilt.Ссылка на вопрос находится здесь: 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;
      }
  }

  1. целые числа влево и вправо устанавливаются в значение каждый раз, когда происходит рекурсия.Что я не понимаю, так это откуда берется это значение, так как я думал, что нужно использовать метод root.val.Можете ли вы объяснить это в терминах непрофессионала?

  2. Когда метод postOrder возвращает left + right + rootval, куда возвращается метод?Как это используется с рекурсивным методом?

1 Ответ

0 голосов
/ 20 сентября 2018

Я думаю, что вас смущает то, что вычисление суммы левого и правого поддерева и вычисление наклона для каждого узла объединено в одном методе.Итак, я упростил код, который вы предоставили, чтобы его было легче понять, и добавил к нему комментарии.Хотя этот способ гораздо менее эффективен, потому что вы вычисляете сумму для левого и правого поддерева каждого узла (при каждом вызове 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;    
    }
}

Надеюсь, что этопоможет!

...