LeetCode Sum of Left Leaves Find the sum of all left leaves in a given binary tree. Example:

    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

---

本题要求二叉树中所有左叶子节点之和。简单题，直接递归，递归的时候记录或判断当前节点是父亲节点的左孩子还是右孩子。完整代码如下： [cpp] class Solution { public: int work(TreeNode *cur, TreeNode *par) { if (cur->left == NULL&&cur->right == NULL&&par->left == cur)return cur->val; int ans = 0; if (cur->left)ans += work(cur->left, cur); if (cur->right)ans += work(cur->right, cur); return ans; } int sumOfLeftLeaves(TreeNode* root) { if (root == NULL)return 0; int sum = 0; if (root->left)sum += work(root->left, root); if (root->right)sum += work(root->right, root); return sum; } }; [/cpp] 本代码提交AC，用时6MS。]]>

226. Invert Binary Tree 226. Invert Binary Tree LeetCode Invert Binary Tree Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

---

本题要把二叉树翻转，看题目中的例子，也就是交换树的左右子树，然后递归的交换就好了。简单题，完整代码如下：

class Solution {
public:
    void invert(TreeNode* root)
    {
        if (root == NULL)
            return;
        swap(root->left, root->right);
        invert(root->left);
        invert(root->right);
    }
    TreeNode* invertTree(TreeNode* root)
    {
        invert(root);
        return root;
    }
};

本代码提交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。

102. Binary Tree Level Order Traversal

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

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

---

本题要求实现二叉树的层次遍历，居然没要求同时实现递归和迭代版本了，不过要求分层输出，还真是头一回见。
层次遍历不难，用队列+BFS实现，但是为了实现分层输出，我的方法是标记下一层的第一个节点，当队列走到下一层第一个节点时，说明该层结束，进入下一个循环。该版本的完整代码如下：

class Solution {
    public: void bfs(vector < vector < int >> & ans, TreeNode * root) {
        queue < TreeNode * > tree;
        tree.push(root);
        TreeNode * front;
        while (!tree.empty()) {
            vector < int > cand;
            bool pushed = false;
            TreeNode * next_level = NULL; // 下一层的第一个节点 
            front = tree.front();
            while (!tree.empty() && front != next_level) {
                tree.pop();
                cand.push_back(front - > val);
                if (front - > left != NULL) {
                    tree.push(front - > left);
                    if (!pushed) {
                        next_level = front - > left; // 标记 
                        pushed = true; // 标记 
                    }
                }
                if (front - > right != NULL) {
                    tree.push(front - > right);
                    if (!pushed) {
                        next_level = front - > right; // 标记 
                        pushed = true; // 标记 

                    }
                }
                if (tree.empty()) break;
                front = tree.front();
            }
            ans.push_back(cand);
        }
    }
    vector < vector < int >> levelOrder(TreeNode * root) {
        vector < vector < int >> ans;
        if (root == NULL) return ans;
        bfs(ans, root);
        return ans;
    }
};

本代码提交AC，用时9MS。
但是这个版本的代码看起来不够简洁，网上看题解发现递归迭代各一种简洁漂亮的解法。
我的解法不够简洁的原因是需要记录下一层第一个节点，然后判断当前层是否已遍历结束。但是仔细想想，这一层需要遍历的次数不就是这一层的节点数吗，而节点都存在队列中了，所以可以获取队列大小n，每层只循环n次即可。这个版本的代码如下，简洁了许多。

class Solution {
    public: vector < vector < int >> levelOrder(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);
        }
        return ans;
    }
};

本代码提交AC，用时6MS，也稍快了一点。
至于递归版本，我是没想到层次遍历也可以用递归来实现。递归的思路是，当当前遍历的层数和结果二维数组中的大小相等时，说明此时是第一次走到这一层，需要往二维数组中加一个空的一维数组，同时把这个节点的值加进去。然后依次先左后右的递归下去。
注意用递归实现层次遍历时，并不和我们肉眼层次遍历的顺序一致，它相当于DFS，只是把深搜的结果存到指定层的数组中了，最终输出的效果和普通的层次遍历一样。递归版本的代码如下：

 class Solution {
     public: void work(vector < vector < int >> & ans, int level, TreeNode * root) {
         if (ans.size() == level) ans.push_back({}); // 重点
         ans[level].push_back(root - > val);
         if (root - > left != NULL) work(ans, level + 1, root - > left); // 先左
         if (root - > right != NULL) work(ans, level + 1, root - > right); // 后右
     }
     vector < vector < int >> levelOrder(TreeNode * root) {
         vector < vector < int >> ans;
         if (root == NULL) return ans;
         work(ans, 0, root);
         return ans;
     }
 };

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