An iterative solution


  • 0
    M
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int findTilt(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int tilt = 0;
            Stack<TreeNode> stack = new Stack<>();
            Map<TreeNode, Integer> map = new HashMap<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.peek();
                if ((node.left == null || map.containsKey(node.left)) &&
                    (node.right == null || map.containsKey(node.right))) {
                    stack.pop();
                    int left = map.containsKey(node.left) ? map.get(node.left) : 0;
                    int right = map.containsKey(node.right) ? map.get(node.right) : 0;
                    tilt += Math.abs(left - right);
                    map.put(node, left + right + node.val);
                } else {
                    if (node.left != null && !map.containsKey(node.left)) {
                        stack.push(node.left); 
                    }
                    
                    if (node.right != null && !map.containsKey(node.right)) {
                        stack.push(node.right);
                    }      
                }
            }
            return tilt;
        }
    }
    

Log in to reply
 

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