## LeetCode Problem: Maximum Depth of Binary Tree

Recursively count the depth of tree node. One node’s depth is the maximum depth of it’s children’s depth + 1 or 0 if node is NULL.

Maximum Depth of Binary Tree Sep 30 ’12
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Code, 64ms pass large set

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(root == NULL) return 0;
int leftdep = maxDepth(root->left);
int rightdep = maxDepth(root->right);
return 1 + std::max(leftdep,rightdep);
}
};
```

## LeetCode Problem: Pascal’s Triangle

The problem is simple, each element in the triangle is the sum of two numbers above it.

So, just build the rows one by one according the row above it. And the first row is {1}.

Pascal’s Triangle Oct 28 ’12
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

```[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
```

Code, 12ms pass large test set

```class Solution {
public:
vector > generate(int numRows) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector >ret;
if(numRows == 0) return ret;
//first row
ret.push_back(vector(1,1));
//rest rows;
for(int nr = 2; nr <= numRows; ++nr) {
vector thisrow(nr,1);
vector &lastrow = ret[nr-2];
for(int ic = 1; ic < nr - 1; ++ic) {
thisrow[ic] = lastrow[ic-1] + lastrow[ic];
}
ret.push_back(thisrow);
}
return ret;
}
};
```

## Algorithm Problem: Find Out the Minimum Number that Great or Equal to a Given Number In BST

Given a BST and a Number k, find out the minimum number p that p >= k.

The method is descriped below, in the code.

The recursive and non-recursive code is included.

```struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
TreeNode *findKRecursive(TreeNode *root, int k) {
if (NULL == root) {
//there is no node that match the requisite.
//在这颗空子树中是找不到目标的
return NULL;
}
if (root->val == k) {
//the node equal to k is find
//找到了正好等于k的节点，这就是全局要找的节点。
return root;
} else if (root->val < k) {
//root is less than k, so the result node is in it's right sub-tree, if there is.
//如果根节点的值小于k，那么唯一的满足条件的节点只能去右子树中查找，如果右子树中没有，那整棵树也没有。
return findKRecursive(root->right, k);
} else {
//root is > k, so the target node may be in it's left sub-tree, or is the current node.
//如果根节点的值>k，那么值更小的满足要求的节点可能出现在左子树中
TreeNode *knode = findKRecursive(root->left, k);
if (knode) {
//if a node is found in left sub-tree, then knode->value must <= cur->value, so return it
//如果左子树中确实找到了一个节点满足要求，那么他的值一定不大于当前节点的值
return knode;
} else {
//or there is no node which value is >= k, then , root is the best choice for the result.
//否则左子树中没有>=k的节点，那最小的满足>=k要求的节点就是root了。
return root;
}
}
}

TreeNode *findK(TreeNode *root, int k) {
TreeNode *lastFound = NULL;//record the last node found which value is >= k
TreeNode *cur = root;//current node to search for.
while (cur) {
if (cur->val == k) {
//the node equal to k is find
//找到了正好等于k的节点，这就是全局要找的节点。
return cur;
} else if (cur->val > k) {
//root is > k, so the result may be in it's left sub-tree, or cur is the best result
//如果根节点的值>k，那么值更小的满足要求的节点可能出现在左子树中，如果左子树没有的话，这就是最好的选择
lastFound = cur;
cur = cur->left;
} else {
//root is less than k, so the result node is in it's right sub-tree, if there is.
//如果根节点的值小于k，那么唯一的满足条件的节点只能去右子树中查找，如果右子树中没有，那整棵树也没有。
cur = cur->right;
}
}
return lastFound;
}
```

## LeetCode Problem: Populating Next Right Pointers in Each Node II

The code in the previous article LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree is also adapted to this situation.

Populating Next Right Pointers in Each Node II
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,

```         1
/  \
2    3
/ \    \
4   5    7
```

After calling your function, the tree should look like:

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

## LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree

It’s easy to doing this by using a queue, doing a level traversal of binary tree.

Populating Next Right Pointers in Each Node
Given a binary tree
}
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,

```         1
/  \
2    3
/ \  / \
4  5  6  7
```

After calling your function, the tree should look like:

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

Code, 160ms pass the large test set.

```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function
queue q;
if(root) {
q.push(root);
q.push(NULL);
}
while(q.size()) {
q.pop();
if(cur) {
cur->next = q.front();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
if (q.size()) q.push(NULL);
}
}
}
};
```

Code rewrite at 2013-1-19, more simple

```class Solution {
public:
queue q;
q.push(root);
q.push(NULL);
while(true) {
q.pop();
if(cur) {
cur->next = q.front();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
if (q.size() == 0 || q.front() == NULL) return;
q.push(NULL);
}
}
}
};
```

## Algorithm Problem:Swap the left and right sub-tree in a binary tree without recursion

Just swap the tree nodes’ left and right child, in the post traversal order.

Code

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void swapLeftAndRight(TreeNode *root) {
bool forward = true;
TreeNode *pre = NULL;
stack trace;
if(root) trace.push(root);

while(trace.size()) {
TreeNode *cur = trace.top();
if(forward) {
if(cur->left && pre != cur->left) {
trace.push(cur->left);
} else {
forward = false;
}
} else {
if(cur->right && pre != cur->right) {
trace.push(cur->right);
forward = true;
} else {
//all the child has finished visit, then swap the left and right of cur
TreeNode *t = cur->left;
cur->left = cur->right;
cur->right = t;

trace.pop();
}
}
pre = cur;
}
}
};
```

## LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

```         1
/ \
2   5
/ \   \
3   4   6
```

The flattened tree should look like:

```   1
\
2
\
3
\
4
\
5
\
6
```

Code:48ms to accept with large test set.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (root == NULL) return;
//1.flat the left subtree
if (root->left)
flatten(root->left);
//2.flatten the right subtree
if (root->right)
flatten(root->right);
//3.if no left return
if (NULL == root->left)
return;
//4.insert left sub tree between root and root->right
//4.1.find the last node in left
TreeNode ** ptn = & (root->left->right);
while (*ptn)
ptn = & ((*ptn)->right);
//4.2.connect right sub tree after left sub tree
*ptn = root->right;
//4.3.move left sub tree to the root's right sub tree
root->right = root->left;
root->left = NULL;

}
};
```

Code rewrite at 2013-2-20, non-recursive version

```class Solution {
public:
void flatten(TreeNode *root) {
bool f = true;
stack t;
TreeNode *pre = NULL;
if(root) {
t.push(root);
}

while(t.size()) {
TreeNode *cur = t.top();
if(f) {
if(cur->left && cur->left != pre) {
t.push(cur->left);
} else {
f = false;
}
} else {
if(cur->right && cur->right != pre) {
t.push(cur->right);
f = true;
} else {
t.pop();
//at this time, the sub-tree of cur is flattened, so just flatten the cur
TreeNode *left = cur->left;
if(left) {
TreeNode *lastLeft = left;
while(lastLeft->right) {
lastLeft = lastLeft->right;
}
lastLeft->right = cur->right;
cur->right = left;
cur->left = NULL;
}
}
}
pre = cur;
}
}
};
```

## LeetCode题目：Convert Sorted List to Binary Search Tree

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.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode *formTree(ListNode *head, int count) {
if(count <= 0) return NULL;
int rootIndex = count / 2;
for(int ir = 0; ir < rootIndex; ++ir) {
rootNode = rootNode->next;
}
TreeNode *root = new TreeNode(rootNode->val);
root->right = formTree(rootNode->next, count - rootIndex - 1);
return root;
}
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function

//1. find the node count, takes O(n) time
int nodeCount = 0;
for(ListNode *cur = head; cur != NULL; cur = cur->next) {
++nodeCount;
}

//2. form the tree with the middle as the root
}
};
```

## LeetCode题目：Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode *sortedArrayToBST(vector &num,int si, int ei) {
if(si > ei) return NULL;
int mid = (ei + si) / 2;
TreeNode *root = new TreeNode(num[mid]);
root->left = sortedArrayToBST(num,si,mid - 1);
root->right = sortedArrayToBST(num,mid + 1,ei);
return root;
}

public:
TreeNode *sortedArrayToBST(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return sortedArrayToBST(num,0,num.size() - 1);
}
};
```

## LeetCode题目：Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *buildTree(vector &iorder, int isi, int iei, vector &porder, int psi, int pei) {
if(iei - isi < 0 || iei - isi != pei - psi) {
return NULL;
}
//the porder[pei] is the root of this tree
TreeNode *root = new TreeNode(porder[pei]);
//find the root in the iorder to seperate it into left sub tree and right sub tree
int riii = -1;//root index in inorder array
for(int i = isi; i <= iei; ++i) {
if(iorder[i] == root->val) {
riii = i;
break;
}
}
if(riii == -1) return root;//error
int lnodes = riii - isi;
//for the left sub tree
//the isi to riii - 1 in inorder array will be it's inorder traversal
//and the psi to psi + lnodes - 1 in postorder array will be it's post order traversal
root->left = buildTree(iorder, isi, riii - 1, porder, psi, psi + lnodes - 1);
//for the right sub tree is similary to the left
root->right = buildTree(iorder, riii + 1, iei, porder, psi + lnodes, pei - 1);
return root;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() -1);
}
};
```

## LeetCode题目：Construct Binary Tree from Preorder and Inorder Traversal

```   1
/   \
2     3
\    /
4  5
```

Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
typedef TreeNode TN;
class Solution {
TN *buildTree(vector &preorder,int psi,int pei,
vector &inorder, int isi, int iei) {
if(pei - psi < 0 || pei - psi != iei - isi)
return NULL;
//root of sub tree
TN *root = new TN(preorder[psi]);
//find this value in inorder to locate the root in inorder
int riii = -1;//root index in inorder
for(int itemp = isi; itemp <= iei; ++ itemp) {
if(inorder[itemp] == root->val) {
riii = itemp;
break;
}
}
if(riii != -1) {
//calculate the nodes count in left tree
int leftCount = riii - isi;
TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
root->left = left;
TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
root->right = right;
}
return root;
}
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
}
};
```

## LeetCode题目：Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

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

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(NULL == root) return ret;

queue que;
que.push(root);
que.push(NULL);//level end point

bool l2r = true;//left to right

vector level;
while(true) {
TreeNode *cur = que.front();
que.pop();
if(cur) {
level.push_back(cur->val);
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
} else {
if(l2r) {
ret.push_back(level);
} else {
vector temp;
for(int i = level.size() - 1 ; i >= 0; --i) {
temp.push_back(level[i]);
}
ret.push_back(temp);
}
level.erase(level.begin(),level.end());
l2r = !l2r;

if(que.size() == 0) break;
que.push(NULL);
}
}

return ret;
}
};
```

## LeetCode题目：Binary Tree Maximum Path Sum

1.终止在这个节点上（往自己子树走）的最大路径值是多少
2.经过这个节点的最大值是多少？（从左子树走过自己到右子树）
3.不经过此节点的子树中可能获得的最大值是多少？

1.终止在此节点的最大路径，首先是自己的值包含进去，然后如果终止在左或右子树的根节点的最大路径值大于0的话，加上这个值。
2.经过这个节点的最大值，很简单了，左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值，直接查看左右子树中的这个值（如果有左右子树的话），还有左右子树的端点最大值。

2013-1-18，更新了一个更简单的办法.

# Question: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

```       1
/ \
2   3
```

Return 6.

# 代码:

## 248ms过大集合

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Maxes{
public:
int tmax;//max of terminated in self
int pmax;//max of pass self
int nmax;//max of non-relative to self
Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
inline int getMax() {
int m = tmax;
if(m < pmax) m = pmax;
if(m < nmax) m = nmax;
return m;
}
};
class Solution {
public:
Maxes maxPath(TreeNode *root) {
Maxes m;
if(NULL == root)
return m;

Maxes l = maxPath(root->left);
Maxes r = maxPath(root->right);

//tmax is the max value which terminated at this node
//when all of it's children is negative, this is it's value
//or add the max value terminated at it's children
m.tmax = max(l.tmax,r.tmax);
if(m.tmax < 0) m.tmax = 0;
m.tmax += root->val;

//pmax is the max value which is pass this node
//that is it's value terminated at it's children (if have, or zero), add self value
m.pmax = l.tmax + r.tmax + root->val;

//nmax is the max value which not including current node
if(root->left)
m.nmax = l.getMax();
if(root->right) {
int rmax = r.getMax();
if(m.nmax < rmax) m.nmax = rmax;
}
return m;
}
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Maxes m = maxPath(root);
int ma = m.getMax();
return ma;
}
};
```

## Code rewrite at 2013-1-18, 266ms pass large set, simpler

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int _curMax;
//return the max path ending in root
//and refresh the _curMax with the path sum that go through from left to root to right child.
int maxWithRoot(TreeNode *root) {
if(NULL == root) return 0;
int leftmax = maxWithRoot(root->left);
int rightmax = maxWithRoot(root->right);

//the max from left child to right child, accross from root
int arcmax = root->val;
if(leftmax > 0) arcmax += leftmax;
if(rightmax > 0) arcmax += rightmax;
if(_curMax < arcmax) _curMax = arcmax;

//the max that end in root
int pathmax = root->val;
int submax = std::max(leftmax,rightmax);
if(submax > 0) pathmax += submax;
if(_curMax < pathmax) _curMax = pathmax;

return pathmax;
}
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
_curMax = INT_MIN;
maxWithRoot(root);
return _curMax;
}
};
```

## LeetCode题目：Binary Tree Level Order Traversal II

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,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

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

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list > retTemp;

queue trace;
trace.push(root);
trace.push(NULL);

vector curLevel;
while(true) {
TreeNode *cur = trace.front();
trace.pop();
if(cur) {
curLevel.push_back(cur->val);
if(cur->left) trace.push(cur->left);
if(cur->right) trace.push(cur->right);
} else {
if(curLevel.size()) {
retTemp.push_front(curLevel);
curLevel.erase(curLevel.begin(),curLevel.end());
trace.push(NULL);
} else {
break;
}
}
}

vector > ret;
for(list >::iterator it = retTemp.begin(); it != retTemp.end(); ++it) {
ret.push_back(*it);
}
return ret;
}
};
```

## LeetCode题目：Binary Tree Level Order Traversal

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,#,#,15,7},

```    3
/ \
9  20
/  \
15   7
```

return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrder(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(NULL == root) return ret;
queue trace;
trace.push(root);
trace.push(NULL);
vector levelVals;
while(true) {
TreeNode *cur = trace.front();
trace.pop();
if(NULL == cur) {
ret.push_back(levelVals);
levelVals.erase(levelVals.begin(),levelVals.end());
if(trace.size())
trace.push(NULL);
else
break;
} else {
levelVals.push_back(cur->val);
if(cur->left) trace.push(cur->left);
if(cur->right) trace.push(cur->right);
}
}
return ret;
}
};
```

Code rewrite at 2012-12-22, 24ms pass the large test set

```class Solution {
public:
vector > levelOrder(TreeNode *root) {
vector > ret;

queue q;
if(root) {
q.push(root);
q.push(NULL);
}

vector level;
while(q.size()) {
TreeNode *cur = q.front();
q.pop();
if(cur) {
level.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
} else {
ret.push_back(level);
level.erase(level.begin(),level.end());
if(q.size()) q.push(NULL);
}
}

return ret;
}
};
```

## LeetCode题目：Validate Binary Search Tree

Validate Binary Search Tree
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.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValid(TreeNode *root, int maxVal, int minVal, bool checkMax, bool checkMin) {
if(NULL == root) return true;
if(checkMax && root->val >= maxVal) return false;
if(checkMin && root->val <= minVal) return false;
bool leftValid = isValid(root->left, root->val, minVal, true, checkMin);
if(!leftValid) return false;
return isValid(root->right, maxVal, root->val, checkMax, true);
}
bool isValidBST(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return isValid(root,0,0,false,false);
}
};
```

## LeetCode题目：Unique Binary Search Trees II

Unique Binary Search Trees II
Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

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

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode *copyTree(TreeNode *root) {
if(NULL == root) return NULL;
TreeNode *croot = new TreeNode(root->val);
croot->left = copyTree(root->left);
croot->right = copyTree(root->right);
return croot;
}
vector generateTrees(int startval,int endval) {
vector ret;
if(endval < startval) {
ret.push_back(NULL);
}
else {
for(int rootval = startval; rootval <= endval; ++rootval) {
vector temp;
{//push root into ret
TreeNode *root = new TreeNode(rootval);
temp.push_back(root);
}
//process the left subtrees
vector lefts = generateTrees(startval, rootval - 1);
int count = temp.size();
for(int ti = 0; ti < count; ++ti) {
TreeNode *root = temp[0];
temp.erase(temp.begin());
for(int li = 0; li < lefts.size(); ++li) {
TreeNode* left = lefts[li];
TreeNode *newroot = copyTree(root);
newroot->left = left;
temp.push_back(newroot);
}
//if(root) delete root;
}
//process the right subtrees
vector rights = generateTrees(rootval + 1, endval);
count = temp.size();
for(int ti = 0; ti < count; ++ ti) {
TreeNode *root = temp[0];
temp.erase(temp.begin());
for(int ri = 0; ri < rights.size(); ++ri) {
TreeNode *copyExpand = copyTree(root);
copyExpand->right = rights[ri];
temp.push_back(copyExpand);
}
//if(root) delete root;
}
for(int i = 0; i < temp.size(); ++i) {
ret.push_back(temp[i]);
}
}
}
return ret;
}
public:
vector generateTrees(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return generateTrees(1,n);
}
};
```

## LeetCode题目：Symmetric Tree

1. 两个节点值相等
2. 左节点的左子树和右节点的右子树对称
3. 左节点的右子树和右节点的左子树对称

Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

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

But the following is not:

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

Note:
Bonus points if you could solve it both recursively and iteratively.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *left, TreeNode *right) {
if(left == NULL) {
return right == NULL;
} else {
if (right == NULL)
return false;
else {
if(left->val != right->val) {
return false;
}
if(!isSymmetric(left->right,right->left)) {
return false;
}
if(!isSymmetric(left->left, right->right)) {
return false;
}
return true;
}
}
}
bool isSymmetric(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root) return true;
return isSymmetric(root->left,root->right);
}
};
```

## LeetCode题目：Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

代码

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
```
1. 递归解法
很简单，8ms过小集合，12ms过大集合

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;
if (NULL == root)
return result;
vector leftResult = inorderTraversal(root->left);
vector rightResult = inorderTraversal(root->right);
for( int i = 0 ; i < leftResult.size(); ++i)
result.push_back(leftResult[i]);
result.push_back(root->val);
for( int i = 0 ; i < rightResult.size(); ++i)
result.push_back(rightResult[i]);
return result;
}
};
```
2. 循环解法
稍复杂点，大小集合都是8ms过

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;

vector trace;
TreeNode *cur = root;
TreeNode *pre = NULL;
bool forward = true;
while(cur)
{
if (forward)
{
//have unvisited left
if (cur->left && pre != cur->left)
{
pre = cur;
trace.push_back(cur);
cur = cur->left;
continue;
}
forward = false;
}
else
{
//not return from right, add self
if(cur->right == NULL || cur->right != pre)
result.push_back(cur->val);
//go right if could
if(cur->right && pre != cur->right)
{
forward = true;
pre = cur;
trace.push_back(cur);
cur = cur->right;
continue;
}
//go up
pre = cur;
if (trace.size() > 0)
{
cur = trace[trace.size() - 1];
trace.pop_back();
} else
cur = NULL;

}
}

return result;
}
};
```
3. 循环解法，2012年12月6日重写，比上一个简洁
```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
if(NULL == root) return ret;

bool forward = true;
stack trace;
TreeNode *preNode = NULL;
trace.push(root);

while(trace.size()) {
TreeNode *curNode = trace.top();
if(forward) {
if(curNode->left && preNode != curNode->left) {
trace.push(curNode->left);
} else {
//no left or left visited
forward = false;
}
} else {
//backward, find sibling(right child)
//if not back from right child, then visit it
if(curNode->right != preNode)
ret.push_back(curNode->val);
if(curNode->right && preNode != curNode->right) {
//if have an unvisited right child, traval it.
trace.push(curNode->right);
forward = true;
} else {
//all sub-tree of this node is visited
trace.pop();
}
}
preNode = curNode;
}

return ret;
}
};
```