LeetCode - Easy - 563. Binary Tree Tilt

红太狼 2022-11-07 15:55 20阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/binary-tree-tilt/][https_leetcode.com_problems_binary-tree-tilt]

Given the `root` of a binary tree, return the sum of every tree node’s **tilt**.

The **tilt** of a tree node is the **absolute difference** between the sum of all left subtree node **values** and all right subtree node **values**. If a node does not have a left child, then the sum of the left subtree node **values** is treated as 0. The rule is similar if there the node does not have a right child.

**Example 1**:

![4b088aeba64d9dc98918c36306144aaa.png][]

Input: root = [1,2,3]
    Output: 1
    Explanation: 
    Tilt of node 2 : |0-0| = 0 (no children)
    Tilt of node 3 : |0-0| = 0 (no children)
    Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
    Sum of every tilt : 0 + 0 + 1 = 1

**Example 2**:

![ca5e1673d094bf4f4a330505c4053d7a.png][]

Input: root = [4,2,9,3,5,null,7]
    Output: 15
    Explanation: 
    Tilt of node 3 : |0-0| = 0 (no children)
    Tilt of node 5 : |0-0| = 0 (no children)
    Tilt of node 7 : |0-0| = 0 (no children)
    Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
    Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
    Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
    Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

**Example 3**:

![37dd2a25686024fa210a0e3714f5eb0e.png][]

Input: root = [21,7,14,1,1,2,2,3,3]
    Output: 9

**Constraints**:

*  The number of nodes in the tree is in the range \[0, 10⁴\].
 *  \-1000 <= Node.val <= 1000

## Analysis ##

运用二叉树的后序遍历算法。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreeTilt { 
    
    	public int findTilt(TreeNode root) { 
    		int[] sum = { 0};
    		findTilt(root, sum);
    		return sum[0];
    	}
    
    	private int findTilt(TreeNode root, int[] sum) { 
    		if (root == null) return 0;
    		int leftSum = findTilt(root.left, sum);
    		int rightSum = findTilt(root.right, sum);
    		sum[0] += Math.abs(leftSum - rightSum);
    		return leftSum + rightSum + root.val;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class BinaryTreeTiltTest { 
    
    	@Test
    	public void test() { 
    		BinaryTreeTilt obj = new BinaryTreeTilt();
    
    		assertEquals(1, obj.findTilt(BinaryTree.integers2BinaryTree(1, 2, 3)));
    		assertEquals(15, obj.findTilt(BinaryTree.integers2BinaryTree(4, 2, 9, 3, 5, null, 7)));
    		assertEquals(9, obj.findTilt(BinaryTree.integers2BinaryTree(21, 7, 14, 1, 1, 2, 2, 3, 3)));
    	}
    	
    }

[https_leetcode.com_problems_binary-tree-tilt]: https://leetcode.com/problems/binary-tree-tilt/
[4b088aeba64d9dc98918c36306144aaa.png]: /images/20221023/54b3fbfd39cd449d8ccc1ff0c9d71db7.png
[ca5e1673d094bf4f4a330505c4053d7a.png]: /images/20221023/cde5ce9f6e96468cbcc96ae5978dda41.png
[37dd2a25686024fa210a0e3714f5eb0e.png]: /images/20221023/e7c17f11ceb84e97af679d969f0c02ea.png