一、重建二叉树
题目：输入某二叉树的先序遍历和中序遍历的结果，请重建二叉树。假如输入的先序遍历和中序遍历的结果都不含重复数字。
例：输入先序遍历序列{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，需要重建二叉树。
节点数据结构：
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
思路：
先序遍历序列的第一个值为二叉树的根节点，利用该根节点在中序遍历中的位置就可以确定树的左子树、右子树，用递归的方法构建该二叉树。
如例，根据先序遍历序列，二叉树的根节点值为1，那么中序遍历序列中可以得出，根节点的左子树的中序遍历序列为{4,7,2}，右子树的中序遍历序列为{5,3,8,6}，于是得到左子树的先序遍历序列为{2,4,7}，右子树的先序遍历序列为{3,5,6,8}。对于左右子树用递归的方法确定其遍历序列，直到创建到叶子节点。
var isSymmetric = function(preorder,inorder) {
if(preorder.length == 0 || inorder.length == 0){
return null;
}
if(preorder.length != inorder.length){
return "invalid input";
}
var preorderStart = 0,
preorderEnd = preorder.length-1,
inorderStart = 0,
inorderEnd = inorder.length-1;
return construct(preorder,preorderStart,preorderEnd,inorder,inorderStart,inorderEnd);
};
var construct = function(preorder,preorderStart,preorderEnd,inorder,inorderStart,inorderEnd){
// 根据先序遍历的第一个节点值确定根节点
var root = new TreeNode();
root.val = preorder[0];
root.left = root.right = null;
if(preorder.length == 1) return root;
// 找到根节点在中序遍历中的位置
var rootIndex = 0;
for(var i=inorderStart;i<=inorderEnd;i++){
if(inorder[i] == root.val){
rootIndex = i;
// 中序遍历中根节点左边的是左子树
root.left = construct(preorder,preoderStart+1,preoderStart+i,inorder,0,i-1);
// 中序遍历中根节点右边的是右子树
root.right = construct(preorder,preoderStart+i+1,preorderEnd,inorder,i+1,inorderEnd);
}
}
return root;
}
二、寻找二叉树的下一个节点
题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
节点的数据结构：
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
this.parent = null;
}
思路：
- 如果该节点有右子树，那么下一个节点就是他的右子树的最左节点
- 如果该节点没有右子树，并且是其父节点的左子节点，那么下一个节点就是他的父节点
- 如果该节点没有右子树，并且是其父节点的右子节点，那么就要向上遍历其父节点和祖先节点，直到找到一个是父节点的左子节点的节点。
var nextNode = function(pNode) {
var pNext = new TreeNode();
if(pNode == null){
return null;
}
// 节点的右子树不为空，节点的下一个节点就为他的右子节点的最左节点
if(pNode.right != null){
pNode = pNode.right;
while(pNode.left != null){
pNode = pNode.left;
}
pNext = pNode;
}else{
// 节点的右子树为空，需要向上遍历父节点
if(pNode.parent == null){ //根节点的下一个节点为null
return null;
}else{
var pCurrent = new TreeNode();
pCurrent = pNode;
var pParent = new TreeNode();
pParent = pCurrent.parent;
// 如果是父节点的右子树，就一直向上遍历，直到找到一个是他父节点的左子节点的节点
// 如果是父节点的左子树，下一个节点就是这个节点的父节点
while(pCurrent != pParent.left){
pCurrent = parent;
pParent = pParent.parent;
}
pNext = pParent;
}
}
};
