LeetCode Array Nesting A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N – 1]. Sets S[K] for 0 <= K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], … }. Sets S[K] are finite for each K and should NOT contain duplicates. Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array. Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

1. N is an integer within the range [1, 20,000].
2. The elements of A are all distinct.
3. Each element of array A is an integer within the range [0, N-1].

---

求嵌套集合的最大长度。首先给定原数组A，嵌套集合为S[K] = { A[K], A[A[K]], A[A[A[K]]], … }，就是不断的把值当下标递归的取值，因为数组A中的值的范围也是0~n-1的，所以下标不会超出范围。 暴力方法就是求出每一个S[K]的大小，然后求最大值。但是仔细分析一个样例就会发现，很多S[K]集合是完全一样的，比如第一个样例中，S[0]和S[2]都等于{5，6，2，0}，因为他们构成了一个循环。所以我们可以创建一个visited数组，访问过就置1，只对哪些visited为0的下标开始递归。这样对于第一个样例，其实只需要3次递归就可以了，也就是下标到值的构成的图中环的个数：{5,6,2,0}，{3}，{1,4}。所以总的复杂度其实只有O(n)。 代码如下： [cpp] class Solution { private: int nest(vector<int> &nums, vector<int> &visited, int k) { int ans = 0; while (visited[k] == 0) { visited[k] = 1; ++ans; k = nums[k]; } return ans; } public: int arrayNesting(vector<int>& nums) { int n = nums.size(); vector<int> visited(n, 0); int ans = 0; for (int i = 0; i < nums.size(); ++i) { if (visited[i] == 0) { int cur = nest(nums, visited, i); ans = max(ans, cur); } } return ans; } }; [/cpp] 本代码提交AC，用时39MS。]]>

LeetCode Construct String from Binary Tree You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree. Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /
  4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \
      4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

---

本题要求把一棵二叉树转换为一个字符串，使用先序遍历的方法，并且左右子树需要用括号括起来，但是要保证从该字符串能唯一恢复回原来的二叉树，而且要去掉不必要的空括号。 首先明确先序遍历：根左右，不难。然后要删掉不必要的空括号，观察第二个样例，发现如果左孩子为空，则左孩子的空括号不能省，但是如果右孩子或者左右孩子都为空，则他们的空括号可以省略。所以分几种情况递归求解即可。 代码如下： [cpp] class Solution { public: string tree2str(TreeNode* t) { if (!t)return ""; if (!t->left && !t->right)return to_string(t->val); if (!t->left)return to_string(t->val) + "()(" + tree2str(t->right) + ")"; if (!t->right)return to_string(t->val) + "(" + tree2str(t->left) + ")"; return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")"; } }; [/cpp] 本代码提交AC，用时19MS。]]>

LeetCode Subtree of Another Tree Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

---

判断二叉树t是否是二叉树s的子树。如果t是s从node0开始的子树，则t必须和node0子树完全一样，node0不能有多余的孩子，比如样例2中node0的子树多有一个节点0，所以是False。 首先写一个子程序check判断子树s和t是否相等，然后在主程序中使用先序遍历s，如果发现s的某个节点node0的值和t的根节点相等，则可以进入check(node0,t)判断node0子树是否和t相等。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; queue<TreeNode*> q; q.push(s); while (!q.empty()) { TreeNode *tmp = q.front(); q.pop(); if (tmp->val == t->val) { if (check(tmp, t))return true; } if (tmp->left != NULL)q.push(tmp->left); if (tmp->right != NULL)q.push(tmp->right); } return false; } }; [/cpp] 本代码提交AC，用时29MS。 还有一种更简洁漂亮的解法。如果t是s的子树，有三种情况，t要么和s完全相等check(s,t)，要么等于s的某个左子树isSubtree(s->left,t)，要么等于s的某个右子树isSubtree(s->right,t)。所以主程序和子程序都可以递归。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; if (check(s, t))return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } }; [/cpp] 本代码提交AC，用时32MS。]]>

LeetCode Optimal Division Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4. However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis. Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant,
since they don't influence the operation priority. So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

1. The length of the input array is [1, 10].
2. Elements in the given array will be in range [2, 1000].
3. There is only one optimal division for each test case.

---

给定一个正整数数组，数据范围是[2,1000]，初始每个数依次除以后一个数，现在要给数组加上括号，使得整个数组相除的结果最大。 首先来个暴力方法，对区间[start, end]，枚举每一个分割位置i，也就是[start, i]算除法，[i+1, end]也算除法，然后把前者的结果除以后者。结果的最大值为前者的最大值除以后者的最小值，结果的最小值为前者的最小值除以后者的最大值。一直递归下去，最后就能得到整个区间[0,n-1]的最大值了。 代码如下： [cpp] struct T { double lfMax, lfMin; string strMax, strMin; }; class Solution { private: T optimal(vector<int>& nums, int start, int end){ T t; if(start == end){ t.lfMax = t.lfMin = nums[start]; t.strMax = t.strMin = to_string(nums[start]); return t; } t.lfMax = std::numeric_limits<double>::min(); t.lfMin = std::numeric_limits<double>::max(); for(int i = start; i < end; ++i){ T tl = optimal(nums, start, i); T tr = optimal(nums, i + 1, end); if(tl.lfMax / tr.lfMin > t.lfMax){ t.lfMax = tl.lfMax / tr.lfMin; t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : ""); } if(tl.lfMin / tr.lfMax < t.lfMin){ t.lfMin = tl.lfMin / tr.lfMax; t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : ""); } } return t; } public: string optimalDivision(vector<int>& nums) { T t = optimal(nums, 0, nums.size() – 1); return t.strMax; } }; [/cpp] 本代码提交AC，用时86MS。暴力方法相当于枚举数组的所有排列情况，时间复杂度为O(n!)。 上述方法对某一小段区间会有很多重复计算，我们可以用数组把结果存起来达到加速的目的。使用数组memo[i][j]存储[i,j]的最大值最小值结果，递归的时候如果发现memo[start][end]已经有结果了，则直接返回。代码如下： [cpp] struct T { double lfMax, lfMin; string strMax, strMin; }; class Solution { private: T optimal(vector<int>& nums, int start, int end, vector<vector<T>>& memo){ if(memo[start][end].strMax != "" || memo[start][end].strMin != "") return memo[start][end]; T t; if(start == end){ t.lfMax = t.lfMin = nums[start]; t.strMax = t.strMin = to_string(nums[start]); memo[start][end] = t; return t; } t.lfMax = std::numeric_limits<double>::min(); t.lfMin = std::numeric_limits<double>::max(); for(int i = start; i < end; ++i){ T tl = optimal(nums, start, i, memo); T tr = optimal(nums, i + 1, end, memo); if(tl.lfMax / tr.lfMin > t.lfMax){ t.lfMax = tl.lfMax / tr.lfMin; t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : ""); } if(tl.lfMin / tr.lfMax < t.lfMin){ t.lfMin = tl.lfMin / tr.lfMax; t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : ""); } } memo[start][end] = t; return t; } public: string optimalDivision(vector<int>& nums) { vector<vector<T>> memo(nums.size(), vector<T>(nums.size())); T t = optimal(nums, 0, nums.size() – 1, memo); return t.strMax; } }; [/cpp] 本代码提交AC，用时6MS。一下快了不少。 还有一种纯数学的方法。假设我们要对a/b/c/d加括号使得结果最大，则a肯定是分子不能动了，那么就相当于最小化b/c/d。b/c/d有两种加括号的方案：b/(c/d)和(b/c)/d。如果令b/(c/d)>b/c/d，因为b,c,d都是正数，推出d>1。又题目中的数据范围是[2,1000]，所以b/(c/d)>b/c/d显然成立。也就是b/c/d这种方案是最小的，使得a/(b/c/d)结果最大。所以只需要把a后面的数加一个括号整体括起来就好了。 代码如下： [cpp] class Solution { public: string optimalDivision(vector<int>& nums) { int n = nums.size(); if(n == 1) return to_string(nums[0]); else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]); string ans = to_string(nums[0]) + "/("; for(int i = 1; i < n – 1; ++i){ ans += to_string(nums[i]) + "/"; } return ans + to_string(nums[n-1]) + ")"; } }; [/cpp] 本代码提交AC，用时3MS。 参考：https://leetcode.com/articles/optimal-division/]]>

LeetCode Binary Tree Tilt 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. 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:

1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
2. All the tilt values won’t exceed the range of 32-bit integer.

---

定义二叉树一个节点的tilt为其左子树元素之和与右子树元素之和的差的绝对值。整棵二叉树的tilt为所有节点的tilt之和。现在要求一棵二叉树的tilt。 简单题，递归求解元素之和，然后更新tilt。都是递归到叶子节点，然后累加和往父亲节点走。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, int& sum, int& tilt){ if(root == NULL) { sum = 0; tilt = 0; } else { int lsum = 0, rsum = 0, ltilt = 0, rtilt = 0; dfs(root->left, lsum, ltilt); dfs(root->right, rsum, rtilt); sum = lsum + rsum + root->val; tilt = ltilt + rtilt + abs(lsum – rsum); } } public: int findTilt(TreeNode* root) { int sum = 0, tilt = 0; dfs(root, sum, tilt); return tilt; } }; [/cpp] 本代码提交AC，用时16MS。]]>

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example:

Input:      1    / \   2   3  / \  / 4  5 6 Output: 6

---

计算完全二叉树的节点个数。如果忽略完全二叉树的性质，像普通二叉树那样进行遍历（先序、中序、后序都可以）统计节点个数，会TLE，所以还是需要用到完全二叉树的性质的。 这里的完全二叉树是指除了最后一层，其他层都是满的，并且最后一层所有节点都是靠左的。具体定义可以看维基百科，下图就是一个完全二叉树的例子： 如果二叉树是满的，比如下面这种，且树的高度是h，则树的节点个数等于$2^h-1$。 那么怎样判断一棵完全二叉树是否是满的呢，只需求一下其极左高度lh和极右高度rh是否相等，如果相等，则是满的，可以用上述公式求解节点数。如果不是满的，则在其左右子树中递归求解节点数，再加上根节点这个节点个数1。 代码如下：

class Solution {
public:
    int countNodes(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = 0, rh = 0;
        TreeNode *l = root, *r = root;
        while (l) {
            ++lh;
            l = l->left;
        }
        while (r) {
            ++rh;
            r = r->right;
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

本代码提交AC，用时82MS。
以上代码还可优化，因为如果知道父亲节点的高度时，其实也就知道了孩子节点的高度了，就是父亲的高度减1，所以在递归时，可以保留高度信息，减少冗余计算。代码如下：

class Solution {
private:
    int height(TreeNode* root, int lh, int rh)
    {
        if (lh == -1) {
            lh = 0;
            TreeNode* l = root;
            while (l) {
                ++lh;
                l = l->left;
            }
        }
        if (rh == -1) {
            rh = 0;
            TreeNode* r = root;
            while (r) {
                ++rh;
                r = r->right;
            }
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return height(root->left, lh – 1, -1) + height(root->right, -1, rh – 1) + 1;
    }
public:
    int countNodes(TreeNode* root) { return height(root, -1, -1); }
};

本代码提交AC，用时55MS，快了一些。