[leetcode]: 563. Binary Tree Tilt

Dear 丶 2022-06-16 13:20 122阅读 0赞

# 1.题目描述 #

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

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  
一棵二叉树，求这棵树的倾斜。  
(1)树的节点的倾斜定义为：ABS(左子树所有节点之和-右子树所有节点的和)  
(2)空节点的倾斜为0  
(3)一棵树的倾斜=该树包含的所有节点的倾斜之和

# 2.分析 #

**树的节点的倾斜定义为：ABS(左子树所有节点之和-右子树所有节点的和)**  
注意是左子树所有节点，而不是一个节点。  
所有有两个要求和的部分：  
1）子树节点求和  
2）子树倾斜求和

# 3.代码 #

int findTilt(TreeNode* root) {
            if (root == NULL)
                return 0;
            int tilt = 0;
            postOrder(root, tilt);//tilt这里是传引用
            return tilt;
        }
        int postOrder(TreeNode* root, int& tilt) {
            if (root == NULL)
                return 0;
            int left = postOrder(root->left,tilt);
            int right = postOrder(root->right, tilt);
            tilt += abs(left - right);//倾斜求和
            return left + right + root->val;//子树节点求和
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Tree)617. Merge Two Binary Trees

1.问题 You are given two binary trees root1 and root2. Imagine that when you put one o

短命女/ 2023年09月26日 20:37/ 0 赞/ 127 阅读

相关 (Java）leetcode-563 Binary Tree Tilt（二叉树的坡度）

题目描述给定一个二叉树，计算整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。整个树的坡度就是其

冷不防/ 2023年02月17日 11:23/ 0 赞/ 7 阅读

相关 LeetCode - Easy - 563. Binary Tree Tilt

Topic Tree Depth-first Search Recursion Description [https://leetcode.co

红太狼/ 2022年11月07日 15:55/ 0 赞/ 20 阅读

相关 Leetcode: Balanced Binary Tree

题目： Given a binary tree, determine if it is height-balanced. For this problem, a heig

傷城~/ 2022年08月07日 04:35/ 0 赞/ 189 阅读

相关 LeetCode-Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

痛定思痛。/ 2022年08月04日 00:57/ 0 赞/ 22 阅读

相关 [leetcode]: 563. Binary Tree Tilt

1.题目描述 Given a binary tree, return the tilt of the whole tree. The tilt of a tree no

Dear 丶/ 2022年06月16日 13:20/ 0 赞/ 123 阅读

相关 leetcode 563. Binary Tree Tilt 二叉树的左右孩子绝对差之和 + DFS深度优先遍历

Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defi

深藏阁楼爱情的钟/ 2022年06月03日 04:16/ 0 赞/ 125 阅读

相关 LeetCode maximum binary tree

Definition for a binary tree node. class TreeNode(object): def

Love The Way You Lie/ 2022年03月15日 18:52/ 0 赞/ 143 阅读

相关刷题leetcode--563. Binary Tree Tilt

2018.1.8路上的风景很精彩！享受过程！![大哭][wail.gif] 563. Binary Tree Tilt![大哭][wail.gif]![大哭][wail.gi

清疚/ 2021年10月09日 03:50/ 0 赞/ 304 阅读

相关 Binary Tree Tilt

Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defi

古城微笑少年丶/ 2021年10月01日 07:56/ 0 赞/ 246 阅读