郑州网站开发公司电话/今日最新新闻摘抄
题目
题解
题目的要求就是求各个节点左右子树和的差
递归遍历二叉树并算出各个节点的子树和
然后中序遍历下该二叉树 求各个节点左右子树差绝对值和
代码
class Solution {
public:void InOrder(TreeNode *root, int &sum) {if (nullptr != root) {if (nullptr == root->left && nullptr == root->right) return;else if (nullptr == root->left) sum += abs(root->right->val);else if (nullptr == root->right) sum += abs(root->left->val);else sum += abs(root->left->val - root->right->val);InOrder(root->left, sum);InOrder(root->right, sum);}}int checkSum(TreeNode *root) {if (nullptr == root->left && nullptr == root->right) return root->val;if (nullptr == root->left) {root->val = checkSum(root->right) + root->val;return root->val;}if (nullptr == root->right) {root->val = checkSum(root->left) + root->val;return root->val;}root->val = checkSum(root->left) + checkSum(root->right) + root->val;return root->val;}int findTilt(TreeNode* root) {if (nullptr == root) return 0;checkSum(root);// cout << sum << endl;int sum = 0;InOrder(root, sum);return sum;}
};