Algo.Java.DFS.Postorder

find sum

    public int doFindSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = doFindTilt(node.left);
        int rightSum = doFindTilt(node.right);

        return leftSum + rightSum + node.val;
    }

find count

    public int doFindCount(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = doFindTilt(node.left);
        int rightSum = doFindTilt(node.right);

        return leftSum + rightSum + 1;
    }

find max abs difference between left and right

/**
 * https://leetcode.com/problems/binary-tree-tilt/description/
 */
public class Main {
    private int sum = 0;

    public static void main(String[] args) {

    }

    public int findTilt(TreeNode root) {
        doFindTilt(root);
        return sum;
    }

    public int doFindTilt(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = doFindTilt(node.left);
        int rightSum = doFindTilt(node.right);
        sum += Math.abs(leftSum - rightSum);
        return leftSum + rightSum + node.val;
    }
}

find max diameter between left and right

 private int diameter = 0;

    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        int maxHeight = doGetMaxHeight(root) -1;
        System.out.println(maxHeight);
        return diameter - 1;
    }

    private int doGetMaxHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = doGetMaxHeight(node.left);
        int right = doGetMaxHeight(node.right);

        int localDiameter = left + right + 1;
        diameter = Math.max(localDiameter, diameter);

        return Math.max(left, right) + 1;
    }
This entry was posted in Без рубрики. Bookmark the permalink.