Subject to introduce

Force buckle 563 questions: leetcode-cn.com/problems/bi…

Analysis of the

From the description of the problem, it is clear that we need to find the slope at each node of a given tree and add all the slopes together to get the final result. To find the slope of any node, we need to find the difference between the sum of all nodes in the left subtree of the node and the sum of all nodes in the right subtree of the node.

So, to find a solution, we use recursive traverse, which returns nodes and below the current node (including itself) when called at any node. By means of the sum of the left and right children of any node, we can directly obtain the slope corresponding to that node.

The code is as follows:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    int result;

    public int findTilt(TreeNode root) {
        traverse(root);
        return result;
    }

    /** * returns the sum */ of all nodes whose root node is the current node
    public int traverse(TreeNode root) {
        if(root == null) {
            return 0;
        }
        // Get the sum of the left subtree nodes
        int left = traverse(root.left);
        // Get the sum of the right subtree nodes
        int right= traverse(root.right);
        // Update the gradient of the binary tree
        result += Math.abs(left - right);
        // Return the sum of all nodes whose root node is the current node
        returnroot.val + left + right; }}Copy the code

Complexity analysis

  • Time complexity: O(n), where nn is the number of nodes. Each node is accessed once.

  • Spatial complexity: O(n), in the worst case, when the tree is tilted, the depth of the tree can reach N. On average, the depth of the tree is logn.