XingXing Park

[Leetcode 719] Find K-th Smallest Pair Distance

Posted on 2018-04-17 | In leetcode | Comments:

原题说明

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

**Example 1**:
Input:
nums = [1,3,1]
k = 1
Output: 0 
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

解题思路

题目要求求出第 k 个最小 pair 的距离。对于长度为n的数组，一共有 n*(n-1)个pair。如果我们求出所有 pair 的距离，然后排序找出第k个最小的pair的距离，时间复杂度会是 O(n^2log(n))，同时空间复杂度会是 O(n^2)，这显然不是最优解。

可以对以上解法稍作优化，使用优先队列进行排序，这样时间复杂度会是O(n^2log(k))，空间复杂度会降低到 O(k)。

这题更好的一个解法是使用 Binary Search。对数组先进行排序，我们可以得到 pair 的最大距离end。因为题目讨论的都是整数，所以答案一定是在0到end的范围内的整数。我们在这个范围内使用 Binary Search，对于每一个搜索的值 mid，我们用一个函数count判断比mid小的 pair 的距离的个数。如果小于k，则让 start == mid ；反之，则让 end == mid。

因为我们对数组事先进行了排序，所以每一次调用count函数，用window sliding的方法，只需要遍历一边数组就可以。

示例代码 (python)

class Solution:
    def smallestDistancePair(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        start, end = 0, nums[-1] - nums[0]
        while start + 1 < end:
            mid = int(start + (end - start)/2)
            if self.count(nums, mid) < k:
                start = mid
            else:
                end = mid
        return start if self.count(nums,start) >= k else end
    
    def count(self, nums, mid): #比mid小的pair数
        left, right, ans = 0, 0, 0
        while right != len(nums):
            while nums[right] - nums[left] > mid:
                left += 1
            ans += right - left
            right += 1
        return ans

示例代码 (cpp)

class Solution {
public:
    int countPairs(vector<int>& nums, int mid) {
        int low = 0, high = 0, res = 0;
        while(high < nums.size()) {
            while(nums[high] - nums[low] > mid) {
                low++;
            }
            res += high - low;
            high++;
        }
        return res;
    }
    
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int low = nums[1] - nums[0], high = nums[nums.size()-1] - nums[0], mid;
        for(int i = 0; i < nums.size() - 1; i++) {
            if (nums[i + 1] - nums[i] < low) {
                low  = nums[i + 1] - nums[i];
            }
        }
        
        while(low < high) {
            mid = (low + high) / 2;
            if (countPairs(nums, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
};

复杂度分析

排序数组的时间复杂度为O(n log(n))， Binary Search的遍历次数为O(log(n))，每次遍历调用 count 函数，需要遍历一边数组，时间复杂度为O(n)，所以总的时间复杂度是O(n log(n))。用 in-place 的方法排序，不需要额外的空间，总的空间复杂度为 O(1)

时间复杂度: O(n log(n))
空间复杂度: O(1)

归纳总结

在有有效精度或者整数等条件给出的前提下，用 Binary Search 往往能有效的优化一些算法。之后我们会再多讨论这类题型。

[Leetcode 777] Swap Adjacent in LR String

Posted on 2018-04-15 | In leetcode | Comments:

原题说明

In a string composed of 'L', 'R', and 'X' characters, like “RXXLRXRXL”, a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Example:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Note:

1 <= len(start) = len(end) <= 10000.
Both start and end will only consist of characters in {'L', 'R', 'X'}.

解题思路

题目要求根据给定的规则，判断能否从 start string 变换到 end string 。

给出了两种变换的规则，从“XL”到“LX”和从“RX”到“XR”。所以我们可以给出两条规律：

如果start能变换到end，那么除去两个字符串中的"X"，剩余的字符串一定相同。因为任意"R"和"L"的相对顺序都不会发生变化，我们定义出去"X"的字符串为有效字符串
根据变换的规则，"L"不能向右移，“R”不能向左移，所以 start 中“L”对应的 index "i" 一定不小于 end 中 “L”对应的index "j"；start 中“R”对应的 index "i" 一定不大于 end 中 “R”对应的index "j"；
1. i >= j, 如果 start[i]==end[j]==”L”
2. i <= j, 如果 start[i]==end[j]==”R”

示例代码 (python)

class Solution:
    def canTransform(self, start, end):
        """
        :type start: str
        :type end: str
        :rtype: bool
        """
        # 第一条规律
        startRemove = "".join(start.split("X"))
        endRemove = "".join(end.split("X"))
        if startRemove != endRemove:
            return False
        # 第二条规律
        i, j, n = 0, 0, len(start)
        while(j < n and i < n):
            while(j < n and end[j] == 'X'):
                j += 1
            while(i < n and start[i] == 'X'):
                i += 1
            if(i == n and j == n): 
                break
            if(start[i] == 'R' and i > j) or (start[i] == 'L' and i < j):
                return False
            i += 1
            j += 1
        return True

复杂度分析

每个字符串遍历一边，时间复杂度为O(n)。没有用额外空间，时间复杂度为O(1)
时间复杂度: O(n)
空间复杂度: O(1)

归纳总结

本题需要对变换的规律做出总结，找出不变量，从而做出进一步判断。

[Leetcode 805] Split Array With Same Average

Posted on 2018-04-12 | In leetcode | Comments:

原题说明

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true    
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].
Read more »

[Leetcode 297] Serialize and Deserialize Binary Tree

Posted on 2018-04-11 | In leetcode | Comments:

原题说明

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

解题思路

本题要求设计两个函数，系列化和反序列化（重构）二叉树。

序列化函数：我们可以用层序遍历的方法将二叉树储存，可以参考[LeetCode 102] Binary Tree Level Order Traversal 二叉树层序遍历，需要注意的一点，遍历过程中，若是当前节点的子节点是空的，我们依然需要储存，这样才能在反序列函数中重构二叉树。

反序列化函数：用队列的数据结构，按层序读取序列，每次读取两个元素，对应当前节点的左右子节点。当序列元素非空时，将其设为当前节点对应的左节点或右节点，并加入队列内。直到读取完所有序列内元素，完成二叉树的重构。

另一种思路是用前序遍历。因为递归的实现比较trivial，这里用递推实现。同样，为了正确重构，我们仍然需要储存空节点。这里我们加入writeAndReturnNode这个辅助函数，让我们可以最大程度的复用原始的递推代码。需要额外注意不要使同一个节点被写一次以上。在解码时，由于在原代码push时不知道右子节点的情况，因此改为push本节点，并在pop时获取正确右子节点状态后，将curr改为右子节点。

示例代码思路一 (python)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "None"
        queue, ans = collections.deque(), collections.deque()
        queue.append(root)
        while queue:
            tmpNode = queue.popleft()
            if tmpNode == None:
                ans.append(tmpNode)
            else:
                ans.append(tmpNode.val)
                queue.extend([tmpNode.left,tmpNode.right])
        return str(list(ans)) #序列返回的结构和题目例子中给出的是一致的
            
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        data = data[1:-1].split(",")
        if not self.represents_int(data[0]) or not data:
            return None
        else:
            root = TreeNode(int(data[0]))
        idx = 1
        queue = collections.deque()
        queue.append(root)
        while idx != len(data):
            tmpNode = queue.popleft()
            if self.represents_int(data[idx]):
                tmpNode.left = TreeNode(int(data[idx]))
                queue.append(tmpNode.left)
            if self.represents_int(data[idx+1]):
                tmpNode.right = TreeNode(int(data[idx+1]))
                queue.append(tmpNode.right)
            idx += 2
        return root

    def represents_int(self, num):
        try: 
            int(num)
            return True
        except ValueError:
            return False
            
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

示例代码思路二 (cpp)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    TreeNode* writeAndReturnNode(TreeNode* node, ostringstream& ret) {
        if (node) {
            ret << node->val << " ";
        } else {
            ret << "X ";
        }
        return node;
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream ret;
        stack<TreeNode*> nodeStack;
        while (writeAndReturnNode(root, ret) || !nodeStack.empty()) {
            while(root) {
                nodeStack.push(root->right);
                root = writeAndReturnNode(root->left, ret);
            }
            if (!nodeStack.empty()) {
                root = nodeStack.top();
                nodeStack.pop();
            }
        }
        return ret.str();
    }

    TreeNode* readAndReturnNode(istringstream& inStream) {
        string nextVal;
        inStream >> nextVal;
        if (nextVal == "X") {
            return NULL;
        } else {
            return new TreeNode(stoi(nextVal));
        }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode *root, *curr, *next;
        stack<TreeNode*> nodeStack;
        istringstream inStream(data);
        root = readAndReturnNode(inStream);
        curr = root;
        while (curr || !nodeStack.empty()) {
            while(curr) {
                curr->left = readAndReturnNode(inStream);
                nodeStack.push(curr);
                curr = curr->left;
            }
            
            if (!nodeStack.empty()) {
                curr = nodeStack.top();
                nodeStack.pop();
                curr->right = readAndReturnNode(inStream);
                curr = curr->right;
            }
        }
        return root;
    }
};

复杂度分析

每个节点被访问一次，同时我们用额外空间（队列/栈）来储存中间过程或答案，所以复杂度分析为
时间复杂度: O(n)
空间复杂度: O(n)

归纳总结

这是一道设计题，对二叉树的序列化和反序列还可以有其它灵活的处理方法。有兴趣的朋友可以再多做一些尝试。

[Leetcode 808] Soup Servings

Posted on 2018-04-10 | In leetcode | Comments:

原题说明

There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:
Input: N = 50
Output: 0.625
Explanation:
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.
Read more »

[Leetcode 236] Lowest Common Ancestor of a Binary Tree

Posted on 2018-04-09 | In leetcode | Comments:

原题说明

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

      _______3______
     /              \
  ___5__          ___1__
 /      \        /      \
6       _2       0       8
        /  \
       7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

解题思路

本题要求找出两个节点的最近的共同祖先。

一个简单的思路是我们可以遍历整棵树，然后用一个map记录每个节点的父节点。这样可以找出节点p和q到根节点的path,然后就能方便的找出最近的共同祖先。但是这样要求我们用额外的map来记录每个节点的信息，空间复杂度为O(n)。

换一个思路，我们发现：假设对于一个节点，如果它的右子树里只找到了其中一个目标节点，而在它的左子树中没有找到另一个目标节点；或者它的左子树里只有一个目标节点，而它的右子树里没有另外一个目标界节点，那么当前节点就不是两个目标节点的最近公共祖先了。除此之外的情况，当前节点就是两个目标节点的公共祖先了。我们可以从叶子节点向上，标记子树中出现目标节点的情况。若一个节点的左右子树都有标记，则当前节点就是共同祖先。

我们用递归的方法实现代码，会非常简洁。

示例代码 (python)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

示例代码 (cpp)

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode *left, *right;
        if (!root || root == p || root == q) {
            return root;
        }
        left = lowestCommonAncestor(root->left, p, q);
        right = lowestCommonAncestor(root->right, p, q);
        if (left && right) {
            return root;
        }
        return left ? left : right;
    }
};

复杂度分析

最坏情况每个节点visit一次，因此时间复杂度为O(n）。
时间复杂度: O(n)
空间复杂度: O(1)

归纳总结

思考清楚共同祖先的定义，我们用递归的方法实现代码。同时我们可以看出，这题本质上还是对 Tree 遍历的变种。

好了，这几天就和大家讨论到这里，种香蕉树去了。

[Leetcode 802] Find Eventual Safe States

Posted on 2018-04-06 | In leetcode | Comments:

原题说明

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]

illustration of graph

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

解题思路

首先需要理解题意, 所谓safe node是指所有经过该node的路径都最后结束于terminal node, 也就是说不会形成环.
所以我们可以给每个node三个状态,分别为:

0: unvisited
1: unsafe
2: safe

利用dfs遍历每一个node (返回值为当前路径是否safe):

如果node的状态为unvisited, 那么我们初始化该node转态为unsafe, 并用dfs遍历其所有路径,如果其中有任意一条范围为unsafe, 那么直接break. 如果所有路径返回均为safe,那么设该node状态为safe并返回.
如果node状态为unsafe, 那么有两种情况, 要么是之前dfs遍历时访问过, 确定为unsafe状态; 要么是当前访问路径下之前经过了该点, 说明当前路径形成了环. 不管是哪一种情况, 当前node的unsafe状态都不会改变, 直接返回false.
如果node状态为safe, 那么肯定是之前dfs遍历过, 确定为safe状态, 直接返回即可.

示例代码 (cpp)

class Solution {
    bool dfs(vector<vector<int>>& graph, vector<int>& states, int cur) {
        if (states[cur] == 1) {
            return false;
        }
        if (states[cur] == 2) {
            return true;
        }
        states[cur] = 1;
        for (auto& nei : graph[cur]) {
            if (!dfs(graph, states, nei)) {
                return false;
            }
        }
        states[cur] = 2;
        return true;
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> states(graph.size(), 0);
        for (int i = 0; i < graph.size(); ++i) {
            dfs(graph, states, i);
        }
        vector<int> rets;
        for (int i = 0; i < states.size(); ++i) {
            if (states[i] == 2) {
                rets.push_back(i);
            }
        }
        return rets;
    }
};

示例代码 (python)

class Solution(object):
    def dfs(self, graph, state, curr_idx):
        if state[curr_idx]:
            return state[curr_idx]
        state[curr_idx] = 1
        for next_node_idx in graph[curr_idx]:
            next_state = self.dfs(graph, state, next_node_idx)
            if next_state == 1:
                return state[curr_idx]
        state[curr_idx] = 2
        return state[curr_idx]
    
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        ret = []
        state = [0 for i in range(len(graph))]
        for idx in range(len(graph)):
            if self.dfs(graph, state, idx) == 2:
                ret.append(idx)
        return ret

复杂度分析

时间复杂度: O(n) 因为每个node经过一次
空间复杂度: O(n) 记录states

归纳总结

这是一道经典的DFS题目, 需要注意的是, 每个node有三个状态, 并且我们经过node时将其设为unsafe状态, 这样遍历过程中再次遇到该点, 我们就可以直接确定为unsafe了.

[Leetcode 117] Populating Next Right Pointers in Each Node II

Posted on 2018-04-05 | In leetcode | Comments:

原题说明

Follow up for problem “Populating Next Right Pointers in Each Node”.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,

Given the following binary tree,

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

解题思路

这题是[LeetCode 116] Populating Next Right Pointers in Each Node的进阶题。从完美二叉树变成任意的二叉树。仍然要求空间复杂度为O(n)。

总体的思路不变，需要记录每层的信息，保存前一个节点，遍历到下一个节点之后，让前一个结点的next链接到当前节点。由于不能保证上一层的父节点都有子节点，因此我们需要对上一层父节点是否存在子节点做出额外的判断，然后遍历当前层的非空节点。这点与之前完美二叉树是不同的。

在示例代码中，prev可以看做一个存放当前遍历节点的前一个节点。而leftMost则指向当前层的第一个节点，遍历完整层后，利用leftMost更新下一层。如果对代码的逻辑理解不够清晰，建议用题目给出的二叉树做简单的验算，能有直观认识。

示例代码 (python)

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        node = root
        while node:
            prev, leftMost = None, None
            while node:
                if node.left:
                    if prev:
                        prev.next = node.left
                    prev = node.left
                    if not leftMost:
                        leftMost = node.left
                if node.right:
                    if prev:
                        prev.next = node.right
                    prev = node.right
                    if not leftMost:
                        leftMost = node.right
                node = node.next
            node = leftMost

示例代码 (cpp)

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *node = root;
        while (node) {
            TreeLinkNode *prev = NULL, *leftMost = NULL;
            while (node) {
                if (node->left) {
                    if (prev) {
                        prev->next = node->left;
                    }
                    prev = node->left;
                    if (!leftMost) {
                        leftMost = node->left;
                    }
                }
                if (node->right) {
                    if (prev) {
                        prev->next = node->right;
                    }
                    prev = node->right;
                    if (!leftMost) {
                        leftMost = node->right;
                    }
                }
                node = node->next;
            }
            node = leftMost;
        }
    }
};

复杂度分析

广度搜索BFS遍历二叉树，每个节点被遍历一次，时间复杂度为O(n）。同时我们使用了cur，pre两个变量，空间复杂度为O(1)。因此复杂度分析为：

时间复杂度： O(n)
空间复杂度： O(1）

总结归纳：

这题是对[LeetCode 116] Populating Next Right Pointers in Each Node的进阶，要求更高。但总体解题的逻辑不变。因此此题的解法也完全适用于Leetcode 166。

种香蕉树去了^_^

[Leetcode 116] Populating Next Right Pointers in Each Node

Posted on 2018-04-05 | In leetcode | Comments:

原题说明

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,

Given the following perfect binary tree,

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

解题思路

本题要去给一个完美二叉树加上next节点，如果没有类似节点则标记为NULL。结合给出的例子，还是题意还是比较清晰的。

最简单的思路，可以结合我们之前层序遍历二叉树的一题 [LeetCode 102] Binary Tree Level Order Traversal 二叉树层序遍历，把每一层的节点按顺序加上next节点即可。然而，这样的空间复杂度会是O(n),并不符合要求。

为了优化空间复杂度，我们需要记录每层的信息，保存前一个节点，遍历到下一个节点之后，让前一个结点的next到当前节点（如果前面没有节点或者当前节点是最后一个，就另行处理）

具体而言，我们用cur记录当前层第一个节点。在每个层间，用pre记录当前节点的前一个节点。如果pre非空，那么把pre.next连接到当前节点root.left,再更新pre。当一层遍历完，就更新到下一层。具体参看代码实例。结合题中给的树的例子和给出的示例代码，能更清晰的理解其中逻辑。

示例代码 (python)

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return
        while root.left:
            cur = root.left
            prev = None
            while root:
                if prev:
                    prev.next = root.left
                root.left.next = root.right
                prev = root.right
                root = root.next
            root = cur

示例代码 (cpp)

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *leftMost = NULL, *prev = NULL;
        while(root) {
            leftMost = root;
            while(root) {
                if (root->left) {
                    if (prev) {
                        prev->next = root->left;
                    }
                    root->left->next = root->right;
                    prev = root->right;
                }
                root = root->next;
            }
            prev = NULL;
            root = leftMost->left;
        }
    }
};

复杂度分析

广度搜索BFS遍历二叉树，每个节点被遍历一次，时间复杂度为O(n）。同时我们使用了cur，pre两个变量，空间复杂度为O(1)。因此复杂度分析为：

时间复杂度： O(n)
空间复杂度：O(1）

总结归纳：

这题题意清晰。为了优化空间复杂度，需要我们对层序遍历做更细致的操作。

以后我们会再介绍本题的进阶版，对非完美二叉树改如何实现同样的操作。基本思路与这题相同，只是需要做更进一步的判断实现next的链接。有兴趣的朋友可以参看

[LeetCode 117] Populating Next Right Pointers in Each Node II

种香蕉树去了^_^

[Leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal

Posted on 2018-04-04 | In leetcode | Comments:

原题说明

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

解题思路

题目给出二叉树的前序遍历与中序遍历，要求重新构建原二叉树，返回根节点。

首先我们需要明确：

前序遍历的顺序：中、左、右
中序遍历的顺序：左、中、右

因此，我们知道前序遍历序列的第一个元素是原二叉树的根节点，而此根节点将中序遍历分为了左子树的中序遍历与右子树的中序遍历。

根据以上思路，我们可以继续对左右子树的分别进行递归，直到序列为空，重构整个二叉树。

示例代码 (python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param inorder, a list of integers
    # @param postorder, a list of integers
    # @return a tree node
    # 12:00
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """ 
        dicinorder = {} #用dictionary记录inoder中value和对应index的关系
        for i, val in enumerate(inorder):
            dicinorder[val] = i
        start, end = 0, len(inorder)
        return self.helper(start, end, preorder, dicinorder)
    
    def helper(self, start, end, preorder, dicinorder):
        if start == end:
            return None
        root = TreeNode(preorder.pop(0))
        inorderIndex = dicinorder[root.val]
        root.left = self.helper(start, inorderIndex, preorder, dicinorder)
        root.right = self.helper(inorderIndex+1, end, preorder, dicinorder)
        return root

复杂度分析

我们使用一个字典记录inorder数组中value与对应index的关系，这样能快速查找每个value的index，每次查找时间复杂度为O(1)。
每个节点重构会被访问一次，一共n个节点。同时字典需要空间O(n)。所以复杂度分析为

时间复杂度: O(n)
空间复杂度: O(n)

归纳总结

此题要求重构二叉树，因此需要理解清楚中序遍历与后序遍历的定义。合理使用递归方法即可完成解题。

大家可以结合利用中序遍历与后序遍历构建二叉树这题，更好的理解问题：

[LeetCode 106] Construct Binary Tree from Inorder and Postorder Traversal

大家可以在 Tree Tag 中找到更多和树有关的内容。种香蕉树去了^_^

猩猩的乐园

技术面试问题详解

RSS

原题说明

解题思路

示例代码 (python)

示例代码 (cpp)

复杂度分析

归纳总结

原题说明

解题思路

示例代码 (python)

复杂度分析

归纳总结

原题说明

原题说明

解题思路

示例代码 思路一 (python)

示例代码 思路二 (cpp)

复杂度分析

归纳总结

原题说明

原题说明

解题思路

示例代码 (python)

示例代码 (cpp)

复杂度分析

归纳总结

原题说明

解题思路

示例代码 (cpp)

示例代码 (python)

复杂度分析

归纳总结

原题说明

解题思路

示例代码 (python)

示例代码 (cpp)

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 (python)

示例代码 (cpp)

复杂度分析

总结归纳：

原题说明

解题思路

示例代码 (python)

复杂度分析

归纳总结

示例代码思路一 (python)

示例代码思路二 (cpp)