Binary Tree Tilt-K6K4.com

原题： https://leetcode.com/problems/binary-tree-tilt/description/

题意： 给定二叉树，计算二叉树的“倾斜值”（tilt）。二叉树节点的倾斜值是指其左右子树和的差的绝对值。空节点的倾斜值为0。

约定：（1）节点和不超过32位整数范围；（2）倾斜值不超过32位整数范围。

例子：

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

标签： tilt、倾斜、binary、tree、node、面试

猜你感兴趣的圈子：

LeetCode交流圈

SLPH

2017-08-12 17:42:10 1楼#1层

Python：

class Solution(object):
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        def subTreeSum(root):
            if not root: return 0
            lsum = subTreeSum(root.left)
            rsum = subTreeSum(root.right)
            self.ans += abs(lsum - rsum)
            return root.val + lsum + rsum
        subTreeSum(root)
        return self.ans

SLPH

2017-08-12 17:42:53 2楼#1层

Java：

public class Solution {  
    private int sum = 0;  
    public int findTilt(TreeNode root) {  
        helper(root);  
        return sum;  
    }  
    private int helper(TreeNode root) {  
        if (root == null)  
            return 0;  
        int left = helper(root.left);  
        int right = helper(root.right);  
        sum += Math.abs(left - right);  
        return root.val + left + right;  
    }  
}

SLPH

2017-08-12 17:43:16 3楼#1层

C++解法一：

class Solution {
public:
    unordered_map<TreeNode*, int> m;
    int findTilt(TreeNode* root) {
        if (!root) return 0;
        int tilt = abs(getSum(root->left, m) - getSum(root->right, m));
        return tilt + findTilt(root->left) + findTilt(root->right);
    }
    int getSum(TreeNode* node, unordered_map<TreeNode*, int>& m) {
        if (!node) return 0;
        if (m.count(node)) return m[node];
        return m[node] = getSum(node->left, m) + getSum(node->right, m) + node->val;
    }
};

SLPH

2017-08-12 17:43:33 4楼#1层

C++解法二：

class Solution {
public:
    int findTilt(TreeNode* root) {
        int res = 0;
        postorder(root, res);
        return res;
    }
    int postorder(TreeNode* node, int& res) {
        if (!node) return 0;
        int leftSum = postorder(node->left, res);
        int rightSum = postorder(node->right, res);
        res += abs(leftSum - rightSum);
        return leftSum + rightSum + node->val;
    }
};

取消

回复

推荐圈子

LeetCode交流圈