263. Ugly Number 263. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

1. 1 is typically treated as an ugly number.
2. Input is within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. 263. Ugly Number

---

本题要判断一个数是否是丑数，丑数的定义是素因子只有2,3,5，简单想法就是不断的除这些数，如果最后结果是1，则说明素因子只有2,3,5，否则还有其他素因子。 完整代码如下：

class Solution {
public:
    bool isUgly(int num)
    {
        if (num < 1)
            return false;
        while (num % 5 == 0)
            num /= 5;
        while (num % 3 == 0)
            num /= 3;
        while (num % 2 == 0)
            num /= 2;
        return num == 1;
    }
};

本代码提交AC，用时3MS。

二刷：

class Solution {
public:
	bool isUgly(int num) {
		if (num <= 0)return false;
		while (num != 1) {
			if (num % 5 == 0)num /= 5;
			else if (num % 3 == 0)num /= 3;
			else if (num % 2 == 0)num /= 2;
			else return false;
		}
		return num == 1;
	}
};

本代码提交AC，用时0MS。

258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?
258. Add Digits

---

题意就是把一个数的每一位相加，如果得到的和大于10，则对和的每一位继续相加，直到最后结果是小于10的。得到的这个数称为数根。 题目要求用O(1)的算法实现，要求好高啊，完全懵*，还是先实现一个常规的迭代算法吧：

class Solution2 {
public:
    int addDigits(int num)
    {
        int sum = num;
        while (sum > 9) {
            int cur_sum = 0;
            while (sum) {
                cur_sum += sum % 10;
                sum = sum / 10;
            }
            sum = cur_sum;
        }
        return sum;
    }
};

本代码提交AC，用时3MS。
后来网上搜索了一下，发现数根有规律，1~20的数根如下：
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
10    1
11    2
12    3
13    4
14    5
15    6
16    7
17    8
18    9
19    1
20    2
每9个一个循环，而且结果是对9取模，但如果是9的倍数的话，结果还是9，所以为了一行搞定，可以用(n-1)%9+1来包括所有的情况。
完整代码如下：

class Solution {
public:
    int addDigits(int num)
    {
        return (num – 1) % 9 + 1;
    }
};

本代码提交AC，用时3MS。

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

---

判断一棵二叉树是否是平衡二叉树。平衡二叉树是指任意子树的左右孩子高度差不超过1。 我最初的想法是DFS找到整棵树的最小和最大高度，然后判断这两个高度差是否超过1，但提交了好几次都只能通过部分样例，好忧伤。 后来看参考网上一个人的题解，还是很厉害的。网上题解都大同小异，思想就是算每棵子树的左右孩子高度差，但是有人是自顶向下的，有人是自底向上的，这里面复杂度当然有差别，如果自顶向下的算，那么很多子树的高度重复计算了，所以采用自底向上的方法比较好，求父亲的高度时，可以用到孩子的高度。 完整代码如下：

class Solution {
public:
    int depth(TreeNode* root)
    {
        if (root == NULL)
            return 0;
        int left = depth(root->left); // 先不断递归到叶子
        int right = depth(root->right);
        if (left < 0 || right < 0)
            return -1;
        if (abs(left – right) > 1)
            return -1;
        return max(left, right) + 1; // 父亲高度利用了孩子的高度
    }
    bool isBalanced(TreeNode* root) { return depth(root) != -1; }
};

本代码提交AC，用时13MS。
二刷。自己写的代码，子函数同时算高度和判断是否平衡，如下：

class Solution {
private:
    bool isBalanced(TreeNode* root, int& height)
    {
        if (root == NULL) {
            height = 0;
            return true;
        }
        int lheight = 0, rheight = 0;
        bool lbalanced = isBalanced(root->left, lheight);
        bool rbalanced = isBalanced(root->right, rheight);
        height = max(lheight, rheight) + 1;
        bool balanced = abs(lheight – rheight) <= 1;
        return lbalanced && rbalanced && balanced;
    }
public:
    bool isBalanced(TreeNode* root)
    {
        int height = 0;
        return isBalanced(root, height);
    }
};

本代码提交AC，用时9MS。

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

---

这一题和之前的LeetCode Convert Sorted Array to Binary Search Tree思路是一样的，只是把数组换成了链表，这样的话，就不能通过下标直接访问到中点元素了。 此时只能通过遍历找到链表的中点，然后以中点为根节点建树，最后分割左右链表，递归建树。完整代码如下：

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head)
    {
        if (head == NULL)
            return NULL;
        if (head->next == NULL)
            return new TreeNode(head->val);
        int n = 0, cnt = 0;
        ListNode* tmp = head;
        while (tmp != NULL) {
            n++;
            tmp = tmp->next;
        }
        tmp = head;
        while (cnt < n / 2 – 1) {
            tmp = tmp->next;
            cnt++;
        } // 此时tmp是中间节点的上一个节点
        TreeNode* root = new TreeNode(tmp->next->val);
        ListNode* head2 = tmp->next->next;
        tmp->next = NULL; // 断开
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(head2);
        return root;
    }
};

本代码提交AC，用时22MS。击败了87%的人:-)
后来想想这题会不会有更优的解法，网上看了一下，发现自己蠢到哭了，链表找中点居然用了这么笨的方法，之前的快慢指针都忘了。换上快慢指针找链表中点的解法如下：

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head)
    {
        if (head == NULL)
            return NULL;
        if (head->next == NULL)
            return new TreeNode(head->val);
        ListNode *fast = head, *slow = head, *prior = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            prior = slow;
            slow = slow->next;
            fast = fast->next->next;
        } // 此时slow为中间节点，prior为中间节点的上一个节点
        TreeNode* root = new TreeNode(slow->val);
        ListNode* head2 = slow->next;
        prior->next = NULL; //断开
        if (head != slow)
            root->left = sortedListToBST(head);
        root->right = sortedListToBST(head2);
        return root;
    }
};

本代码提交AC，用时26MS，有点失望，按理说这种解法是要比我上面的解法快的。
后来我又发现，这两种解法构建出来的平衡二叉搜索树不一样，如下图所示，但是他们都还算紧凑，都是正确的，看来答案不唯一啊。（其实主要是偶数长度时，有两个中间节点，选哪个都是正确的。）

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

---

给定一个升序排列的数组，要构建一个高度平衡的二叉搜索树。 二叉搜索树的概念是递归定义的，具体可以参看维基百科，简单来说就是左孩子小于根节点，右孩子大于根节点。 但是本题要求二叉搜索树是高度平衡的，也就是说左右孩子的高度差不能大于1。 我一开始的想法是既然是平衡二叉搜索树，直接取数组中点，然后左右依次排开，肯定能得到一棵平衡二叉搜索树，如下左图所示。 但是这一版本的代码提交上去之后只通过了6个样例。后来仔细想了想，这解法未免也太简单幼稚了吧。想到之前解树的题都用到了递归，这题应该也可以用，立马灵光一闪，第一次取中点之后，递归的在左右半个数组中取中点建树，所有还可以得到如上右图所示的更加紧凑的平衡二叉搜索树。

完整代码如下：

class Solution {
public:
    TreeNode* work(vector<int>& nums, int s, int t)
    {
        if (s == t)
            return new TreeNode(nums[s]);
        if (s > t)
            return NULL;
        int mid = (s + t + 1) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = work(nums, s, mid – 1);
        root->right = work(nums, mid + 1, t);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) { return work(nums, 0, nums.size() – 1); }
};

本代码提交AC，用时16MS。

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

---

不知道这一题存在的必要性在哪里，解题方法和上一题LeetCode Binary Tree Level Order Traversal一模一样，不管是递归还是迭代，都只要在最后把结果reverse一下就好了。
完整代码如下：

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode* root)
    {
        vector<vector<int> > ans;
        if (root == NULL)
            return ans;
        queue<TreeNode*> tree;
        tree.push(root);
        TreeNode* f;
        while (!tree.empty()) {
            int n = tree.size();
            vector<int> one_level;
            for (int i = 0; i < n; i++) {
                f = tree.front();
                tree.pop();
                one_level.push_back(f->val);
                if (f->left != NULL)
                    tree.push(f->left);
                if (f->right != NULL)
                    tree.push(f->right);
            }
            ans.push_back(one_level);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

本代码提交AC，用时6MS。

二刷。还可以借助栈：

class Solution {
public:
	vector<vector<int>> levelOrderBottom(TreeNode* root) {
		if (root == NULL)return {};

		stack<vector<int>> stk;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			int n = q.size();
			vector<int> cur_level;
			while (n--) {
				TreeNode* front_tn = q.front();
				q.pop();
				cur_level.push_back(front_tn->val);
				if (front_tn->left != NULL)q.push(front_tn->left);
				if (front_tn->right != NULL)q.push(front_tn->right);
			}
			stk.push(cur_level);
		}
		vector<vector<int>> ans;
		while (!stk.empty()) {
			ans.push_back(stk.top());
			stk.pop();
		}
		return ans;
	}
};

本代码提交AC，用时4MS。