563. Binary Tree Tilt 두 갈래 나무의 경사도

2159 단어
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. 한두 갈래의 나무를 정해 나무 전체의 경사도를 되돌려준다.기울기는 왼쪽 트리 및 오른쪽 트리 및 의 절대값 차이로 정의됩니다.빈 노드의 경사도는 0입니다.전체 나무의 경사도는 모든 결점 경사도의 합으로 정의됩니다.
Example: 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
Note:
  • The sum of node values in any subtree won't exceed the range of 32-bit integer.
  • All the tilt values won't exceed the range of 32-bit integer.

  • 사고방식의 뒷부분을 두루 돌아다니며 두루 돌아다니는 과정에서 좌우 서브트리의 결점과 전역 변수를 사용하여 현재 노드의 경사도를 기록한다.
    /**
     * 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 {
    private:
        int res=0;
        int postOrder(TreeNode* root){
            if(!root) return 0;
            int left=postOrder(root->left);
            int right=postOrder(root->right);
            res+=abs(left-right);
            return left+right+root->val;
        }
    public:
        int findTilt(TreeNode* root) {
            postOrder(root);
            return res;
        }
    };
    

    또는 전역 변수를 사용하지 않고 매개 변수로 변경합니다.
    /**
     * 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 {
    private:
        int postOrder(TreeNode* root, int& res){
            if(!root) return 0;
            int left=postOrder(root->left,res);
            int right=postOrder(root->right,res);
            res+=abs(left-right);
            return left+right+root->val;
        }
    public:
        int findTilt(TreeNode* root) {
            int res=0;
            postOrder(root,res);
            return res;
        }
    };
    

    좋은 웹페이지 즐겨찾기