DFS C++/Python


  • 0
    Z

    c++

    /**
     * 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 {
    public:
        int findTilt(TreeNode* root) {
            int diff = 0;
            dfs(root, diff);
            return diff;
        }
    
        int dfs(TreeNode * root, int & diff) {
            if ( NULL == root ) {
                return 0;
            }
            int left = dfs(root->left, diff);
            int right = dfs(root->right, diff);
            diff += abs(left - right);
            return left + root->val + right;
        }
    };
    

    python

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def findTilt(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(root):
                if not root:
                    return 0
                left = dfs(root.left)
                right = dfs(root.right)
                diff[0] += abs(left - right)
                return left + root.val + right
            diff = [0]
            dfs(root)
            return diff[0]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.