LeetCode-Binary Tree

LeetCode中涉及到二叉树的几道题目。记录recursive和iterative两种思路。

在整理之前先看一下二叉树节点的定义

1
2
3
4
5
6
7
8
9
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

关于BST树

Binary Tree Inorder Traversal(No.94)

Given a binary tree, return the inorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]

Recursive solution

考察的是中序遍历的方法,首先是的recursive的方式,实现起来思路也比较简单,模拟中序遍历的过程,先从左子树开始,然后根节点,再右子树。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> result;
void helpsort(TreeNode* root){
if(root != NULL ){
helpsort(root->left);
result.push_back(root->val);
helpsort(root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
helpsort(root);
return result;
}
};

Iterative solution

LeetCode在题目下面就提到了

Follow up: Recursive solution is trivial, could you do it iteratively?

也就是让我们除了递归的方法外,再试一试迭代的方式解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if (root == NULL) return res;
stack<TreeNode*> stck;
TreeNode* curr=root;

while (curr || !stck.empty()) {
while (curr) {
stck.push(curr);
curr = curr->left;
}
curr = stck.top(), stck.pop();
res.push_back(curr->val);
curr = curr->right;
}

return res;
}
};

一般会用堆栈的结构去模拟像递归那样的过程,因为本质上递归也是一个利用堆栈的实现方式。

Kth Smallest Element in a BST(No.230)

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3

在考虑这道题的时候。求第k小的值,那么因为BST树的性质,按照中序遍历一遍就会从小到大获得一串序列,那么谁是第k小的值也就知道了。其实和上一题差不多。

Recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
helper(root, k, res);
return res[k-1];
}
void helper(TreeNode* root, int k, vector<int>& res){
if(res.size() == k){
return;
}
if(root != NULL){
helper(root->left, k, res);
res.push_back(root->val);
helper(root->right, k, res);
}
}
};

Iterative solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
if(root == NULL) return false;
stack<TreeNode*> vessel;
TreeNode* curr = root;
while(curr != NULL || !vessel.empty()){
while(curr){
vessel.push(curr);
curr = curr->left;
}
curr = vessel.top(); vessel.pop(); k--;
if(k == 0) break;
curr = curr->right;
}
return curr->val;
}
};

Validate Binary Search Tree(No.98)

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

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

既然需要验证这个二叉树是不是二叉搜索树,自然而然想到了如果满足二叉搜索树的性质,那么中序遍历出来的一定是一个升序的序列。如果中序遍历出的结果不满足升序的话说明这个二叉树不是二叉搜索树。

Recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> inorder;
void inorderTraversal(TreeNode* root){
if(root){
inorderTraversal(root->left);
inorder.push_back(root->val);
inorderTraversal(root->right);
}
}
bool isValidBST(TreeNode* root) {
if(root==NULL) return true;
inorderTraversal(root);
for(int i=0;i<inorder.size()-1;i++){
if(inorder[i+1]<=inorder[i])
return false;
}
return true;
}
};

还有一种在discussion里看到的思路,就是检查每一个节点处的大小值情况,根节点值要大于左子树的最大值,小于右子树的最小值。否则就报错,然后一层层迭代下去。最后测下来这种写法其实没直接中序遍历来的快。这个方法12ms,上面的解法4ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root == NULL) return true;
if(root->left != NULL)
{
TreeNode* leftmax = root->left;
while(leftmax->right != NULL) leftmax = leftmax->right;
if(root->val <= leftmax->val) return false;
}
if(root->right != NULL)
{
TreeNode* rightmin = root->right;
while(rightmin->left != NULL) rightmin = rightmin->left;
if(root->val >= rightmin->val) return false;
}
return isValidBST(root->left) && isValidBST(root->right);
}
};

其他关于二叉树的题目

Sum of Left Leaves(No.404)

Find the sum of all left leaves in a given binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int sumOfLeftLeaves(TreeNode* root) {
int sum=0;
if(!root) return 0;
if(root->left!=NULL)
{
if(!root->left->left&&!root->left->right)
sum+=root->left->val;
else
sum+=sumOfLeftLeaves(root->left);
}

if(root->right!=NULL)
{
sum+=sumOfLeftLeaves(root->right);
}
return sum;
}

更漂亮的写法:

1
2
3
4
5
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
if (root->left && !root->left->left && !root->left->right) return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}

Binary Tree Level Order Traversal II(No.107)

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]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void levelOrder(TreeNode* root, vector<vector<int> > &v, int currLevel) {
if (root == NULL) {
return false;
}
if (v.empty() || currLevel > (v.size() - 1)) {
v.push_back(vector<int>());
}
v[currLevel].push_back(root->val);
levelOrder(root->left, v, currLevel + 1);
levelOrder(root->right, v, currLevel + 1);
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ret;
levelOrder(root,ret,0);
reverse(ret.begin(), ret.end());
return ret;
}
};

Convert Sorted Array to Binary Search Tree(No.108)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* sortedArrayToBST(vector<int>& num) {
if(num.size() == 0) return NULL;
if(num.size() == 1)
{
return new TreeNode(num[0]);
}

int middle = num.size()/2;
TreeNode* root = new TreeNode(num[middle]);

vector<int> leftInts(num.begin(), num.begin()+middle);
vector<int> rightInts(num.begin()+middle+1, num.end());

root->left = sortedArrayToBST(leftInts);
root->right = sortedArrayToBST(rightInts);

return root;
}

Maximum Depth of Binary Tree(No.104)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxDepth(TreeNode* root){
return root == NULL ? 0 : max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
}
int max(int a,int b)
{
return (a>=b)? a:b;
}

};