543. Diameter of Binary Tree

https://leetcode.com/problems/diameter-of-binary-tree/description/

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Thoughts

返回二叉树任意两点所形成的路径中长度最长的路径的长度，长度为路径中边的数目。二叉树=>分治。对于给定的结点node，分别有三种情况：diameter在左子树，diameter在右子树以及diameter穿过当前结点。如果只存储和返回当前结点所在子树的diameter，则不能知道left diameter本身到底是上面的哪三种构成的，而且即使知道了也不能直接利用（只有当node.left是diameter终点时才能直接和当前点加起来形成新的diameter）。因此需要额外global变量res存最终结果。问的是path长度，因此return时+1用来计入从cur往上申出的边。

Code

/*
 * @lc app=leetcode id=543 lang=cpp
 *
 * [543] Diameter of Binary Tree
 */

// @lc code=start
/**
 * 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 res = 0;
    int dfs(TreeNode *cur) {
        if (cur == nullptr) return 0;
        int l = dfs(cur->left);
        int r = dfs(cur->right);
        res = max(res, l + r);
        return max(l, r) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }
};
// @lc code=end

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {   
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right); // no plus one here

        return Math.max(left, right) + 1;
    }
}

Analysis

时间复杂度O(n).

Ver.2

Iterative solution based on post-order traversal. diameters记录两个值, 左中右连起来的长度和只有左中或右中的长度最大值. 前者用于算最长的可能值, 后者用于最为子结果喂给父节点.

/**
 * 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;
    }
}