OJ每日练习（17）

Posted on | In

题目名称

  1. Construct Binary Tree
  2. Unique Binary Search Trees（Leetcode #96）
  3. Validate Binary Search Tree（Leetcode #98）
  4. Convert Sorted Array to Binary Search Tree（Leetcode #108）
  5. Convert Sorted List to Binary Search Tree（Leetcode #109）
  6. Minimum Depth of Binary Tree (Leetcode #111)
  7. Path Sum (Leetcode #112)
  8. Binary Tree Maximum Path Sum (Leetcode #124)
  9. Populating Next Right Pointers in Each Node（Leetcode #116）
  10. Sum Root to Leaf Numbers(Leetcode #129）

Construct Binary Tree

解题思路

从中序+前序，以及中序+后序可以重建完全二叉树，其具体思想就是普通的递归（递归基是起点大于终点），现给出二者的实现方案。

解题方案

Pre+In:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
        if(pre.empty())
            return nullptr;
        if(pre.size()==1)
            return new TreeNode(pre[0]);
        return aux(pre,0,pre.size()-1,in,0,in.size()-1);
    }
private:
    TreeNode* aux(vector<int>& pre,int pb,int pe,vector<int>& in,int ib,int ie) {
        if(pb>pe || ib>ie) return nullptr;
        int rootVal = pre[pb];
        TreeNode* root = new TreeNode(rootVal);
        int pos=0;
        while(in[pos]!=rootVal) ++pos;
        root->left = aux(pre,pb+1,pb+pos-ib,in,ib,pos-1);
        root->right = aux(pre,pb+1+pos-ib,pe,in,pos+1,ie);
        return root;
    }
};

In+Post:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode* buildTree(vector<int>& in, vector<int>& post) {
        if (in.empty())
			return nullptr;
		if (in.size() == 1)
			return new TreeNode(in[0]);
		return aux(in,0,in.size()-1,post,0,post.size()-1);
    }
private:
    TreeNode* aux(vector<int>& in,int ib,int ie,vector<int>& post,int pb,int pe){
        if(ib>ie || pb>pe)
            return nullptr;
        int rootVal = post[pe];
        TreeNode* root = new TreeNode(rootVal);
        int pos =0;
        while(in[pos]!=rootVal) ++pos;
        root->left = aux(in,ib,pos-1,post,pb,pb+pos-1-ib);
        root->right = aux(in,pos+1,ie,post,pb+pos-ib,pe-1);
        return root;
    }
};

Unique Binary Search Trees（Leetcode #96）

题目描述

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

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

解题思路

这是卡特兰数的典型实例。举例而言，当构成元素为1~n时，以i为根节点的树，其左子树由[1,i-1]构成，右子树由[i+1,n]构成。定义f(i)为以[1,i]构成的BST的个数，显然，
f(0)=0,f(1)=1,f(2)=f(0)*f(1)+f(1)*f(0),f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)(一个乘式对应着一个root），因此不难得出结论：

最终将问题转为一维动态规划求解。

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0]=1,dp[1]=1;
        for(int i=2;i<=n;++i)
            for(int k=1;k<=i;++k)
                dp[i]+=dp[k-1]*dp[i-k];
        return dp[n];
    }
};

扩展（Unique Binary Search TreesⅡ Leetcode#95)

题目描述

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

解题思路

针对每一个根递归求解。具体来说，当beg>end时，插入nullptr并return。（递归基）否则构建左右子树的vector，并遍历其元素以作为左右子树。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n==0) return vector<TreeNode*>();
        return aux(1,n);
    }
private:
    vector<TreeNode*> aux(int beg,int end){
        vector<TreeNode*> res;
        if(beg>end){
            res.push_back(nullptr);
            return res;
        }    
        for(int i=beg;i<=end;++i){
            vector<TreeNode*> leftsubs = aux(beg,i-1);
            vector<TreeNode*> rightsubs = aux(i+1,end);
            for(auto nl:leftsubs)
                for(auto nr:rightsubs){
                    TreeNode* root = new TreeNode(i);
                    root->left=nl;
                    root->right=nr;
                    res.push_back(root);
                }
        }
        return res;
    }
};

Validate Binary Search Tree（Leetcode #98）

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

解题思路

第一反应是中序遍历二叉树，观察其中是否存在逆序对，这是一个可行的解，此外也可以使用递归实现（设定max与min，观察每一个节点是否超出，每下一层都更新min与max）

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return aux(root,LONG_MIN,LONG_MAX);
    }
private:
    bool aux(TreeNode* root,long min,long max){
        if(!root) return true;
        if(root->val <= min || root->val >= max) return false;
        return aux(root->left,min,root->val) && aux(root->right,root->val,max);
    }
};

Convert Sorted Array to Binary Search Tree（Leetcode #108）

解题思路

非常简单的题目。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return aux(nums,0,nums.size()-1);
    }
private:
    TreeNode* aux(vector<int>& nums,int beg,int end){
        if(beg>end)
            return nullptr;
        int middle = beg+(end-beg)/2;
        TreeNode* root = new TreeNode(nums[middle]);
        root->left = aux(nums,beg,middle-1);
        root->right = aux(nums,middle+1,end);
        return root;
    }
};

Convert Sorted List to Binary Search Tree（Leetcode #109）

解题思路

这道题的难度相较于上一道大了不少，主要原因在于单链表不支持随机访问。但原理总是类似的，我们可以采用快慢指针的方式，首先找到中点，然后完成求解。值得注意的是，在寻找中点时需要记录中点的前一个节点，以便于完成单链表的切断。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) 
            return nullptr;
        if(!head->next) 
            return new TreeNode(head->val);
        ListNode *p = head, *q = head, *pre=nullptr;
        while (q && q->next) {
            pre = p;
            p = p->next;
            q = q->next->next;
        }
        pre->next = nullptr;
        TreeNode *root = new TreeNode(p->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(p->next);
        return root;
    }
};

Minimum Depth of Binary Tree (Leetcode #111)

题目描述

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Example:

1
2
3
4
5
6
7
8
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

解题思路

非常简单的题目，遍历两个子树的min深度即可。值得注意的是若某个子树高度为0，最低高度是另一个子树的高度+根节点。

解题方案

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minDepth(TreeNode* root) {
       if (!root) return 0;
	    int left = minDepth(root->left);
	    int right = minDepth(root->right);
	    return (left == 0 || right == 0) ? left + right + 1 : min(left, right) + 1;
    }
};

扩展

若是求解max，难度更低：

1
2
3
4
5
6
7
8
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

扩展

若是求解n叉树的maxDep，步骤几乎一样：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxDepth(Node* root) {
        if(!root)
            return 0;
        int res=0;
        for(auto n:root->children)
            res=max(maxDepth(n),res);
        return res+1;
    }
};

Path Sum (Leetcode #112)

题目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Example:

1
2
3
4
5
6
7
8
9
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解题思路

朴素深搜，找到了直接return。

解题方案

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)
            return false;
        if(!root->left && !root->right && root->val==sum)
            return true;
        return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};

扩展（

题目描述

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given the below binary tree and sum = 22,
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Return:
[
   [5,4,11,2],
   [5,8,4,5]
]

解题思路

这道题的思路与上一题类似，但区别在于找到了不能直接return，需要接着往下探索，当某个节点探索完毕后需要对cur执行pop_back;

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int> > res;
        vector<int> cur;
        aux(root,sum,res,cur);
        return res;
    }
private:
    void aux(TreeNode* root, int sum,vector<vector<int> >&res, vector<int> &cur){
        if(!root)
            return;
        cur.push_back(root->val);
        if(!root->left && !root->right && root->val==sum)
            res.push_back(cur);
        aux(root->left,sum-root->val,res,cur);
        aux(root->right,sum-root->val,res,cur);
        cur.pop_back();
    }
};

Binary Tree Maximum Path Sum (Leetcode #124)

题目描述

Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example1:

1
2
3
4
5
Input: [1,2,3]
       1
      / \
     2   3
Output: 6

Example2:
1
2
3
4
5
6
7
Input: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
Output: 42

解题思路

这道题十分类似于最长子序列和，但二叉树并不像array那样可以线性遍历，因此可以采取这样的策略：求解左子树，若其值为正，那么对结果有利，可以加上，接着求解右子树，若其对结果有利，也加上。需要注意的是，最后返回只返回了一个方向，这是因为递归需要返回root，不可能出现left->root->right的情况。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int res=INT_MIN;
        aux(root,res);
        return res;
    }
private:
    int aux(TreeNode* root,int& res){
        if(!root) return 0;
        int left=max(0,aux(root->left,res));
        int right=max(0,aux(root->right,res));
        res=max(res,left+right+root->val);
        return max(left,right)+root->val;
    }
};

Populating Next Right Pointers in Each Node（Leetcode #116）

解题思路

这道题比昨天的要简单一些，因为这是一颗满二叉树。因此可以采用递归解决。具体来说就是始终连接左-右，右-兄弟之左或右-nullptr。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void connect(TreeLinkNode *root) {
        aux(root,nullptr);
    }
private:
    void aux(TreeLinkNode *root,TreeLinkNode *next){
        if(!root) return;
        root->next=next;
        aux(root->left,root->right);
        aux(root->right,next?next->left:nullptr);
    }
};

Sum Root to Leaf Numbers(Leetcode #129）

题目描述

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Example 1:

1
2
3
4
5
6
7
8
9
Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

解题思路

朴素深搜即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return aux(root,0);
    }
public:
    int aux(TreeNode* root,int sum){
        if(!root)
            return 0;
        if(!root->left && !root->right)
            return sum*10+root->val;
        return aux(root->left,sum*10+root->val)+aux(root->right,sum*10+root->val);
    }
};