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 {
        private void pushLeft(Stack<TreeNode> stack, TreeNode node, Stack<int[]> diameters) {
            while (node != null) {
                stack.push(node);
                diameters.push(new int[]{1, 1});
                node = node.left;
            }
        }
        
        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int max = Integer.MIN_VALUE;
            Stack<TreeNode> stack = new Stack<>();
            // <diameter with left and right, max diameter with left or right>
            Stack<int[]> diameters = new Stack<>();  
            pushLeft(stack, root, diameters);
            TreeNode pre = null;
            int[] preRes = new int[2];
            while (!stack.isEmpty()) {
                TreeNode node = stack.peek();
                int[] diameter = diameters.peek();
                diameter[0] = diameter[0] + preRes[1];
                diameter[1] = Math.max(diameter[1], 1 + preRes[1]);
                if (node.right != null && node.right != pre) {
                    pushLeft(stack, node.right, diameters);
                    preRes = new int[2];
                    continue;
                }
                stack.pop();
                diameters.pop();
                max = Math.max(max, diameter[0]);
                pre = node;
                preRes = diameter;
            }
            
            return max - 1;
        }
    }
    

Log in to reply
 

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