Tag Archives:

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N
以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N
输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。

样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。
简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
	parent[node] = pre;
	graph[node][pre] = 0;
	graph[pre][node] = 0;
	for (int i = 1; i <= n; ++i) {
		if (graph[node][i] == 1) {
			DFS(i, node);
		}
	}
	graph[node][pre] = 1;
	graph[pre][node] = 1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	int a, b;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	DFS(k, 0);
	for (int i = 1; i <= n; ++i)
		printf("%d ", parent[i]);
	return 0;
}

本代码提交AC,用时42MS。

LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1: 

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

The following are two duplicate subtrees:

      2
     /
    4

and

    4

Therefore, you need to return above trees' root in the form of a list.


给定一棵二叉树,要求找出其中的重复子树,每组重复子树输出其中一个子树即可。
去重最好的办法就是hash,所以思想是把每个子树hash到一个unordered_map中,如果有多个子树hash到同一个桶,则出现了重复。
所以问题的关键是怎样对一个子树hash。我们可以把一棵子树表示成 (left_hash, root, right_hash),其中left_hash和right_hash分别是左子树和右子树的hash字符串,root表示当前根节点的hash字符串。所以这是一个递归定义。规定空节点的hash值为空串""。
根据子树hash的定义,叶子节点的hash值是("",val,"")。求解子树hash值的过程可以用中序遍历,左根右。为什么子树hash中需要逗号和括号呢,就是为了保证不同严格区分不同的子树,因为单纯的中序遍历是无法区分某些子树的,比如下面的两个子树,中序遍历结果都是2,1,无法区分;但是用本文的hash方法,得到的hash值分别是(2,1,)和(,2,1),这两个字符串是有区别的。

  1
 /
2

 2
  \
   1

在DFS的过程中,把每个子树的hash值记录到一个unordered_map中,然后遍历unordered_map,如果该桶放了多个子树,则取出其中一个即可。
完整代码如下:

class Solution {
private:
	string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
		if (root == NULL)return "";
		string left = DFS(root->left, inorders);
		string right = DFS(root->right, inorders);
		string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
		inorders[cur].push_back(root);
		return cur;
	}
public:
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
		unordered_map<string, vector<TreeNode*>> inorders;
		DFS(root, inorders);
		vector<TreeNode*> ans;
		for (auto &it : inorders) {
			if (it.second.size() > 1)
				ans.push_back(it.second[0]);
		}
		return ans;
	}
};

本代码提交AC,用时52MS。

LeetCode Design Search Autocomplete System

LeetCode Design Search Autocomplete System
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

  1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
  2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
  3. If less than 3 hot sentences exist, then just return as many as you can.
  4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical dataSentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.
 
Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:
Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix "i ".
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a".
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
 
Note:

  1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
  2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
  3. Please use double-quote instead of single-quote when you write test cases even for a character input.
  4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see herefor more details.

本题要求实现一个搜索引擎的自动补全功能,正好是我想在我的新闻搜索引擎里实现的功能。首先会给出一些历史数据,就是哪些句子被访问了多少次。现在模拟用户输入,每输入一个字符,给出以输入的所有字符为前缀的历史句子,并且只给出被访频率前3的句子作为自动补全的候选。
Trie树的应用题。Trie树的节点属性包含is_sentence_以该字符结尾是否是一个句子,cnt_该句子的频率。首先把历史数据插入到Trie树中,记录好相应的is_sentence_和cnt_。
用一个成员变量cur_sentence_记录当前输入的字符串前缀。查找的时候,用cur_sentence_在Trie树中找,先找到这个前缀,然后在26个字母+一个空格中递归查找所有孩子节点,把能形成句子的字符串及其频率插入到一个优先队列中。该优先队列先以句子频率排序,如果频率相等,再以字典序排列。这样我们直接从优先队列中取出前三个堆顶句子,就是自动补全的候选。
如果遇到#,说明输入结束,把cur_sentence_及其频率1也插入到Trie树中。注意插入之后树中节点的频率是累加的,即第34行。
注意AutocompleteSystem类初始化的时候需要清空cur_sentence_和Trie树,更多的细节请看代码中的caution。

const int N = 26;
class AutocompleteSystem {
private:
	struct Node {
		bool is_sentence_;
		int cnt_;
		vector<Node*> children_;
		Node() :is_sentence_(false), cnt_(0){
			for (int i = 0; i < N + 1; ++i)children_.push_back(NULL);
		}
	};
	Node *root;
	string cur_sentence_;
	struct Candidate {
		int cnt_;
		string sentence_;
		Candidate(int &cnt, string &sentence) :cnt_(cnt), sentence_(sentence) {};
		bool operator<(const Candidate& cand) const {
			return (cnt_ < cand.cnt_) || (cnt_ == cand.cnt_&&sentence_ > cand.sentence_); // caution
		}
	};
	void AddSentence(const string& sentence, const int& time) {
		Node *cur = root;
		for (const auto& c : sentence) {
			int idx = c - 'a';
			if (c == ' ')idx = N;
			if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
			cur = cur->children_[idx];
		}
		cur->is_sentence_ = true;
		cur->cnt_ += time; // caution
	}
	void FindSentences(Node *root, string &sentence, priority_queue<Candidate>& candidates) {
		if (root != NULL&&root->is_sentence_)candidates.push(Candidate(root->cnt_, sentence));
		if (root == NULL)return;
		for (int i = 0; i < N + 1; ++i) {
			if (root->children_[i] != NULL) {
				if (i == N)
					sentence.push_back(' ');
				else
					sentence.push_back('a' + i);
				FindSentences(root->children_[i], sentence, candidates);
				sentence.pop_back();
			}
		}
	}
	void StartWith(priority_queue<Candidate>& candidates) {
		Node *cur = root;
		for (const auto& c : cur_sentence_) {
			int idx = c - 'a';
			if (c == ' ')idx = N;
			if (cur->children_[idx] == NULL)return;
			cur = cur->children_[idx];
		}
		string sentence = cur_sentence_;
		FindSentences(cur, sentence, candidates);
	}
public:
	AutocompleteSystem(vector<string> sentences, vector<int> times) {
		root = new Node(); // caution
		cur_sentence_ = ""; // caution
		for (int i = 0; i < sentences.size(); ++i)AddSentence(sentences[i], times[i]);
	}
	vector<string> input(char c) {
		if (c == '#') {
			AddSentence(cur_sentence_, 1); // caution
			cur_sentence_ = ""; // caution
			return{};
		}
		else {
			cur_sentence_.push_back(c);
			priority_queue<Candidate> candidates;
			StartWith(candidates);
			if (candidates.empty())return{};
			vector<string> ans;
			while (!candidates.empty()) {
				ans.push_back(candidates.top().sentence_);
				candidates.pop();
				if (ans.size() == 3)break;
			}
			return ans;
		}
	}
};

本代码提交AC,用时329MS。

LeetCode Average of Levels in Binary Tree

LeetCode Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

  1. The range of node's value is in the range of 32-bit signed integer.

求二叉树每一层的平均数。简单题,BFS层次遍历。代码如下:

class Solution {
public:
	vector<double> averageOfLevels(TreeNode* root) {
		if (root == NULL)return{};
		vector<double> ans;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			double sum = 0;
			size_t n = q.size();
			for (size_t i = 0; i < n; ++i) {
				TreeNode* f = q.front();
				q.pop();
				sum += f->val;
				if (f->left != NULL)q.push(f->left);
				if (f->right != NULL)q.push(f->right);
			}
			ans.push_back(sum / n);
		}
		return ans;
	}
};

本代码提交AC,用时15MS。

LeetCode Add and Search Word - Data structure design

LeetCode Add and Search Word - Data structure design
Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

实现一个字典,要求可以插入单词和搜索单词,并且支持一种正则表达式,即点号'.'表示任意一个字符。
本题明显是用Trie树来做,插入和搜索普通字符串的方法和Trie树是一模一样的。
唯一需要注意的是搜索带点号的字符串,此时用递归来做,递归的出口是,当遍历到字符串的最后一个字符时,根据是否为点号进行判断。递归向下的过程也是分是否为点号的,如果是点号,则需要尝试26种递归路径。想清楚这个逻辑之后,代码就很好写了。
完整代码如下:

const int N = 26;
class WordDictionary {
private:
	struct Node {
		bool isWord;
		vector<Node*> children;
		Node(bool i) :isWord(i) {
			for (int i = 0; i < N; ++i)children.push_back(NULL);
		};
	};
	Node *root;
	bool search(const string& word, int i, Node *root) {
		if (root == NULL)return false;
		int idx = word[i] - 'a';
		if (i == word.size() - 1) {
			if (word[i] != '.')return root->children[idx] != NULL&&root->children[idx]->isWord;
			else {
				for (int j = 0; j < N; ++j) {
					if (root->children[j] != NULL&&root->children[j]->isWord)return true;
				}
				return false;
			}
		}
		if (word[i] != '.')return search(word, i + 1, root->children[idx]);
		else {
			for (int j = 0; j < N; ++j) {
				if (search(word, i + 1, root->children[j]))return true;
			}
			return false;
		}
	}
public:
	/** Initialize your data structure here. */
	WordDictionary() {
		root = new Node(false);
	}
	/** Adds a word into the data structure. */
	void addWord(string word) {
		Node *cur = root;
		for (const auto& c : word) {
			int idx = c - 'a';
			if (cur->children[idx] == NULL)cur->children[idx] = new Node(false);
			cur = cur->children[idx];
		}
		cur->isWord = true;
	}
	/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
	bool search(string word) {
		Node *cur = root;
		return search(word, 0, cur);
	}
};

本代码提交AC,用时105MS。

LeetCode Range Sum Query - Mutable

LeetCode Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。
第一敏感使用线段树,很久之前在hihoCoder上遇到过
建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。
查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。
更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。
完整代码如下:

class NumArray {
private:
	struct Node {
		int start, end, sum;
		Node *left, *right;
		Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {};
	};
	Node *root;
	Node* constructTree(vector<int> &nums, int start, int end) {
		Node* node = new Node(start, end);
		if (start == end) {
			node->sum = nums[start];
			return node;
		}
		int mid = start + (end - start) / 2;
		node->left = constructTree(nums, start, mid);
		node->right = constructTree(nums, mid + 1, end);
		node->sum = node->left->sum + node->right->sum;
		return node;
	}
	int sumRange(int i, int j, Node *root) {
		if (root == NULL)return 0;
		if (i == root->start&&j == root->end)return root->sum;
		int mid = root->start + (root->end - root->start) / 2;
		if (j <= mid)return sumRange(i, j, root->left);
		else if (i > mid)return sumRange(i, j, root->right);
		else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right);
	}
	void update(int i, int val, Node *root) {
		if (root->start == root->end && root->start == i) {
			root->sum = val;
			return;
		}
		int mid = root->start + (root->end - root->start) / 2;
		if (i <= mid)update(i, val, root->left);
		else update(i, val, root->right);
		root->sum = root->left->sum + root->right->sum;
	}
public:
	NumArray(vector<int> nums) {
		root = NULL;
		if (!nums.empty())root = constructTree(nums, 0, nums.size() - 1);
	}
	void update(int i, int val) {
		if (root == NULL)return;
		update(i, val, root);
	}
	int sumRange(int i, int j) {
		if (root == NULL)return 0;
		return sumRange(i, j, root);
	}
};

本代码提交AC,用时172MS。

LeetCode Implement Trie (Prefix Tree)

LeetCode Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.


本题要求实现只包含26个小写字母的trie树。因为之前做过hihoCoder 1014-Trie树,所以实现起来并不费劲。
定义一个Node结构体,包含三个成员,char c表示该Node的字符,bool isWord表示以该Node结尾是否能构成一个单词,children表示该Node的26个孩子。
初始化的时候就初始化一个根节点。
插入一个单词时,不断从根节点往下创建节点,到最后一个字符所在节点时,标记isWord为true。
搜索一个单词时,也是不断从根节点往下搜索,如果到单词尾所在的Node的isWord为true,说明找到该单词,否则要么到不了最后一个字符,要么到了最后一个字符,isWord为false,都表示搜索失败。
搜索是否有某个前缀的单词存在,和搜索一个单词几乎一样,只不过最后返回时,不需要判断isWord是否为true,只要能到达prefix的最后一个字符的Node,说明后面肯定有以该字符串为前缀的单词存在。
完整代码如下:

const int MAXN = 26;
class Trie {
private:
	struct Node
	{
		char c;
		bool isWord;
		Node(char c_, bool isWord_) :c(c_), isWord(isWord_) {
			for (int i = 0; i < MAXN; ++i)children.push_back(NULL);
		};
		vector<Node*> children;
	};
	Node *root;
public:
	/** Initialize your data structure here. */
	Trie() {
		root = new Node(' ', true);
	}
	/** Inserts a word into the trie. */
	void insert(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)cur->children[idx] = new Node(word[i], false);
			cur = cur->children[idx];
		}
		cur->isWord = true;
	}
	/** Returns if the word is in the trie. */
	bool search(string word) {
		Node *cur = root;
		for (int i = 0; i < word.size(); ++i) {
			int idx = word[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return cur->isWord;
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
		Node *cur = root;
		for (int i = 0; i < prefix.size(); ++i) {
			int idx = prefix[i] - 'a';
			if (cur->children[idx] == NULL)return false;
			cur = cur->children[idx];
		}
		return true;
	}
};

本代码提交AC,用时118MS。

LeetCode Add One Row to Tree

LeetCode Add One Row to Tree
Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.
The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:

Input:
A binary tree as following:
       4
     /   \
    2     6
   / \   /
  3   1 5
v = 1
d = 2
Output:
       4
      / \
     1   1
    /     \
   2       6
  / \     /
 3   1   5

Example 2:

Input:
A binary tree as following:
      4
     /
    2
   / \
  3   1
v = 1
d = 3
Output:
      4
     /
    2
   / \
  1   1
 /     \
3       1

Note:

  1. The given d is in range [1, maximum depth of the given tree + 1].
  2. The given binary tree has at least one tree node.

在二叉树深度为d的那一层增加一行值全为v的节点,如果d=1的话,新增一个值为v的根节点,原来的树作为新根节点的左子树。
简单题,层次遍历到深度为d-1时,对d-1层的所有节点,都增加值为v的左右孩子,如果d-1层的节点原来有左右孩子,则原来的左右孩子接到新加入的v的节点上,作为左右孩子。
完整代码如下:

class Solution {
public:
	TreeNode* addOneRow(TreeNode* root, int v, int d) {
		if (d == 1) {
			TreeNode* newRoot = new TreeNode(v);
			newRoot->left = root;
			return newRoot;
		}
		queue<TreeNode*> tree;
		tree.push(root);
		int depth = 0;
		while (!tree.empty()) {
			++depth;
			int n = tree.size();
			if (depth == d - 1) {
				for (int i = 0; i < n; ++i) {
					TreeNode* p = tree.front();
					tree.pop();
					if (p == NULL)continue;
					TreeNode* l = new TreeNode(v);
					l->left = p->left;
					p->left = l;
					TreeNode* r = new TreeNode(v);
					r->right = p->right;
					p->right = r;
				}
				break;
			}
			else {
				for (int i = 0; i < n; ++i) {
					TreeNode* p = tree.front();
					tree.pop();
					if (p == NULL)continue;
					tree.push(p->left);
					tree.push(p->right);
				}
			}
		}
		return root;
	}
};

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

LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree
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.


给定一棵二叉树和两个节点p,q,问p和q的最近公共祖先节点是哪个。LCA问题
思路:要找p和q的最近公共祖先,很直观的方法是找到从根节点分别到p和q的路径,然后把其中一条路径(比如根到p)上的点hash成path1,从另一条路径(比如根到q)的底端(q)往根节点走,把走过的每个点去path1中找,如果找到,则就是他们的LCA,因为这是距离q最近、且在path1中的点。
但是怎样找到根到p和q的路径呢。这里换一种思路,定义如下新的数据结构,par表示该节点的父节点,根节点的父节点为-1。

struct MyNode {
	TreeNode* node;
	int par;
	MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};

先整体把树层次遍历一遍,成为一个保存MyNode的数组,记录每个点的父节点在数组中的下标。在遍历的同时,记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。
找到路径之后,对其中一条路径hash,另一条路径在该hash中找。代码如下:

class Solution {
private:
	struct MyNode {
		TreeNode* node;
		int par;
		MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
	};
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<MyNode> nodes;
		int i = 0, j = 0;
		queue<MyNode> tree;
		tree.push({ root,-1 });
		while (!tree.empty()) {
			MyNode cur = tree.front();
			tree.pop();
			if (cur.node == NULL) continue;
			if (cur.node == p)i = nodes.size();
			if (cur.node == q)j = nodes.size();
			tree.push({ cur.node->left,nodes.size() });
			tree.push({ cur.node->right,nodes.size() });
			nodes.push_back(cur);
		}
		if (i == j)return nodes[i].node;
		unordered_set<int> path1;
		while (i != -1) {
			path1.insert(i);
			i = nodes[i].par;
		}
		while (j != -1) {
			if (path1.find(j) != path1.end()) {
				return nodes[j].node;
			}
			j = nodes[j].par;
		}
		return NULL;
	}
};

本代码提交AC,用时19MS。
讨论区还有一种递归的解法,很有意思。我们在以root为根的树中找p和q的LCA,如果root等于p或q其中之一,说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA,如果发现在左右子树中找到的LCA都不为null,说明他们p和q分别位于root的两个子树,类似样例中的5和1,则root就是他们的LCA。如果某个子树返回的LCA为空,说明p和q都不在这个子树中,则先遇到谁,谁就是LCA,比如样例中的5和4,都不在3的右子树,在递归3的左子树的时候,先遇到了5,所以5是LCA。
完整代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (root == NULL || root == p || root == q)return root;
		TreeNode* left = lowestCommonAncestor(root->left, p, q);
		TreeNode* right = lowestCommonAncestor(root->right, p, q);
		if (left != NULL&&right != NULL)return root;
		return left != NULL ? left : right;
	}
};

本代码提交AC,用时23MS。

LeetCode Merge Two Binary Trees

LeetCode Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:

Input:
	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
Output:
Merged tree:
	     3
	    / \
	   4   5
	  / \   \
	 5   4   7

Note: The merging process must start from the root nodes of both trees.


上午又参加了一场LeetCode的比赛,第三题花了不少时间,第四题在11:06分AC了,但是比赛好像在11:00就结束了。。。无语,排名只有376。
这题要求把两棵二叉树合并,如果对应位置都有节点,则新节点的值等于两个老节点的值之和,否则等于有值的那个节点。
简单题,直接递归merge就好。代码如下:

class Solution {
public:
	TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
		if (t1 == NULL&&t2 == NULL)return NULL;
		if (t1 == NULL&&t2 != NULL)return t2;
		if (t1 != NULL&&t2 == NULL)return t1;
		TreeNode* left = mergeTrees(t1->left, t2->left);
		TreeNode* right = mergeTrees(t1->right, t2->right);
		TreeNode* root = new TreeNode(t1->val + t2->val);
		root->left = left;
		root->right = right;
		return root;
	}
};

本代码提交AC,用时49MS。