563. Binary Tree Tilt

发布时间：2020-12-14 04:19:26 所属栏目：大数据来源：网络整理

导读：https://leetcode.com/problems/binary-tree-tilt/description/ 挺好的一个题目，审题不清的话很容易做错。主要是tilt of whole tree 的定义是sum of all node‘s tilt 而不是想当然的tilt of root. 一开是我就以为是简单的tilt of root 导致完全错误。思路

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

挺好的一个题目，审题不清的话很容易做错。主要是tilt of whole tree 的定义是sum of all node‘s tilt 而不是想当然的tilt of root.

一开是我就以为是简单的tilt of root 导致完全错误。思路其实可以看作是求sum of children 的变种，只是这里不仅要跟踪每个子树的sum 还要累计上他们的tilt。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    int tiltIter(TreeNode* root,int *t) {
        if (root == nullptr) {
            return 0;
        }
        
        int leftSum = 0;
        int rightSum = 0;
        if (root->left != nullptr) {
            leftSum = tiltIter(root->left,t);
        }
        if (root->right != nullptr) {
            rightSum = tiltIter(root->right,t);
        }
        //tilt of the current node;
        int tilt = abs(leftSum - rightSum);
        *t += tilt;
        return root->val + leftSum + rightSum;
    }
    
    int findTilt(TreeNode* root) {
        int tilt = 0;
        tiltIter(root,&tilt);
        return tilt;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!