Leetcode 563 二叉树的坡度

　　JAVA BFS：

public final int findTilt(TreeNode root) {
        if (root == null) return 0;
        Map<TreeNode, Integer> cacheMap = new HashMap<TreeNode, Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int res = 0;
        queue.add(root);
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                TreeNode node = queue.poll();
                res += Math.abs(getSum(node.left, cacheMap) - getSum(node.right, cacheMap));
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return res;
    }

    private final int getSum(TreeNode node, Map<TreeNode, Integer> cacheMap) {
        if (node == null) return 0;
        if (cacheMap.containsKey(node)) return cacheMap.get(node);
        int res = getSum(node.left, cacheMap) + getSum(node.right, cacheMap) + node.val;
        cacheMap.put(node, res);
        return res;
    }

　　JAVA DFS：

　　int res = 0;

    public final int findTilt(TreeNode root) {
        find(root);
        return res;
    }

    private final int find(TreeNode root) {
        if (root == null) return 0;
        int left = find(root.left);
        int right = find(root.right);
        res += Math.abs(left - right);
        return left + right + root.val;
    }

　　JS BFS：

var findTilt = function (root) {
    if (!root) return 0;
    let find = (node, cacheMap) => {
        if (!node) return 0;
        if (cacheMap.get(node)) return cacheMap.get(node);
        let currentRe = find(node.left, cacheMap) + find(node.right, cacheMap) + node.val;
        cacheMap.set(node, currentRe);
        return currentRe;
    }
    let queue = [], res = 0, cacheMap = new Map();
    queue.push(root);
    while (queue.length > 0) {
        let currentLength = queue.length;
        for (let i = 0; i < currentLength; i++) {
            let currentNode = queue.shift();
            res += Math.abs(find(currentNode.left, cacheMap) - find(currentNode.right, cacheMap));
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }
    }
    return res;
}

　　JS DFS：

var findTilt = function (root) {
    let res = 0;
    let find = (node) => {
        if (!node) return 0;
        let left = find(node.left), right = find(node.right);
        res += Math.abs(left - right);
        return left + right + node.val;
    }
    find(root);
    return res;
};