学步园

一、已知某二叉树的前序遍历结果和中序遍历结果，请重构该二叉树。

解题思路：根据前序遍历第一个值可以得到根节点，然后在中序遍历中找到跟节点，位于该节点前的值组成二叉树的左子树，位于该节点后的值组成二叉树的右子树。然后递归构造左子树和右子树。

函数的参数和返回值：组成某个子树需要一串数值，我们需要知道这串数值在前序遍历序列和中序遍历序列中的初始下边和终点下标，该函数返回该子树的根节点指针。

代码实现：

struct BTN
{
    int value;
    BTN* pLeft;
    BTN* pRight;
};

BTN* construct(BTN* preOrderStart,BTN* inOrderStart,int length){
  if(preOrderStart == NULL || inOrderStart == NULL || length < 0)
    return NULL;
  constructChildTree(preOrderStart,preOrderStart+length-1,inOrderStart,inOrderStart+length-1);
}

BTN* constructChildTree(BTN* preOrderStart,BTN* preOrderEnd,BTN* inOrderStart,BTN* inOrderEnd){
  //根据前序遍历确定根节点
  int rootValue = preOrderStart[0];
  BTN root = new BTN();
  root->value = rootValue;
  root->pLeft = NULL;
  root->pRight = NULL;

  //终止递归的条件，序列中只有一个节点
  if(preOrderStart == preOrderEnd){
    if(inOrderStart == inOrderEnd && *preOrderStart == *inOrderStart)
      return root;
    else
    //如果前序遍历序列和中序遍历序列中都只有一个值但是它们不相等，则输入序列有误
      throw std::exception("Invalid input.");
  }

  //在中序遍历序列中找出根节点所在的下标
  BTN* inOrderRoot = inOrderStart;
  while(inOrderRoot <= inOrderEnd && *inOrderRoot != rootValue)
    inOrderRoot++;
  //如果找到最后也没有发现跟根节点值相同的节点，则输入序列有误
  if(inOrderRoot == inOrderEnd && *inOrderRoot != *inOrderEnd)
    throw std::exception("Invalid input.");
  int lengthOfLeftChild = inOrderRoot - inOrderStart;
  BTN* preOrderEndOfLeftChild = preOrderStart + lengthOfLeftChild;
  //构建左子树
  if(lengthOfLeftChild > 0)
    root->pLeft = constructChildTree(preOrderStart+1,
          preOrderEndOfLeftChild,inOrderStart,inOrderRoot-1);
  //构建右子树
  if(lengthOfLeftChild < preOrderEnd - preOrderStart)
    root->pRight = constructChildTree(preOrderEndOfLeftChild+1,
          preOrderEnd,inOrderRoot+1,inOrderEnd);
  return root;
}

二、判断某个输入序列是否是某个二叉搜索树的后续遍历序列

代码：

bool isSequenceOfBST(int sequence[],int length){
  if(sequence == NULL || length <= 0)
    return false;
  int root = sequence[length - 1];
  int i = 0;
  for(;i < length; i++){
    if(sequence[i] > 0)
      break;
  }
  int j = i;
  for(;j < length;j++){
    if(sequence[j] < root)
      return false;
  }
  bool left = true;
  if(i > 0)
    left = isSequenceOfBST(sequence,i);
  bool right = true;
  if(i < length)
    right = isSequenceOfBST(sequence + i, length - i);
  return (left && right);
}

三、非递归实现前序遍历二叉树

利用栈实现递归：

void preOrderBinaryTree(BinaryTreeNode * pRoot){
    std::stack<BinaryTreeNode *> sData;
    if(pRoot == NULL)
        return;
    sData.push(pRoot);
    BinaryTreeNode * pNode = NULL;

    while(!sData.empty()){
        pNode = sData.top();
        printf("%d ",pNode -> value);
        sData.pop();
        
        if(pNode -> right != NULL){
            sData.push(pNode -> right);
        }
        if(pNode -> left != NULL){
            sData.push(pNode -> left);
        }
    }
}

四、二叉树中和为某一个值的路径

输入一个二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。分析及代码：

//为什么不用栈，因为用栈只能得到栈首元素，不能打印该序列
//为什么只要存当前的遍历过的序列的和，而不是每遍历一个存一下前面所有元素的和，因为如果用递归的方法
//你入栈的时候先把右子节点入栈，然后入左子结点，而到左子结点的路径上节点的和是不包括右子节点的
//为什么定义两个函数，因为我们需要一个值存现在遍历的元素的和，一个队列保存现在遍历的节点，这些是共享的
//而不是要放到一个函数里，如果这些定义在一个函数里，那么它们只是这一个函数作用域的变量，而不是一个公共的变量
void isValue(BinaryTreeNode* pRoot,int value){
  if(pRoot == null)
    return;
  vec.push_back(pRoot);
  std::vector<int> vec;
  int currValue = 0;
  isValue(BinaryTreeNode* pRoot,vector & vec,int & currValue,int value);
}
void isValue(BinaryTreeNode* pRoot,std::vector<int>& vec,int & currValue,int value){
  //每次进来的时候先把节点入栈，然后判断它是不是叶子节点，如果是的话看现在路径上节点的和是不是给出的值
  //如果是就打印该路径，如果不是那么就把这个节点弹出回到它的父节点
  currValue += pRoot -> value;
  vec.push_back(pRoot -> value);

  if(pRoot -> left == NULL && pRoot -> right == NULL && currValue == value){
    std::vector<int>:: iterator = vec.begin();
    for(;iterator != vec.end();iterator++)
      printf("%d ",*iterator);
  }
  if(pRoot -> left != NULL)
    isValue(pRoot -> left,vec,currValue,value);
  if(pRoot -> right != NULL)
    isValue(pRoot -> right,vec,currValue,value);
  currValue -= pRoot -> value;
  vec.pop_back();
}

五、已知一个二叉树的根节点和叶子结点，打印从根结点到叶子结点的路径。

思路分析：假设有一个二叉树A(B(D(F,G),E(H,I)),C)，自己画一下，每层分别为A,BC,DE,FGHI，我们打印从A到H的路径。怎么做呢，我们可以定义一个vector用来存放这个路径

上的结点，用前序遍历。首先是根节点A，放入vector，其次是B，放入vector，然后是D，放入vector，最后我们将F放入vector。我们发现，F是叶子结点了，从F是到达不了

H的，于是将F踢出vector，访问D的右结点，将G放入vector我们发现G是叶子结点也是到达不了H的，于是将G踢出vector。由此我们可以知道从D是到达不了H的，将D也踢出

去，接着访问B的右子结点E，我们也是先将其放入vector，再往下到达H，将H放入vector，一条完整的路径就出现了。

在这个过程中，我们做了什么呢？我们整体要做的是前序遍历，每当遍历一个结点时我们会先判断这个结点是不是我们题目中给出的叶子结点，如果不是那么放入

vector，当发现这个结点的左右子树的叶子结点中没有我们要找的结点时，这个点要被踢出去。如果我们设这个函数为getNodePath，那么对于其左右子结点要循环调用这个函

数，因为我们需要知道左右子结点是否包含题中给出的叶子结点，所以这个函数要返回一个bool类型的值。我们需要一个全局的vector来存放路径，所以这个要作为函数的参

数。

bool getNodePath(BinaryTreeNode * pRoot,BinaryTreeNode * pNode,vector<BinaryTreeNode*>& path){
  //如前所说，这是在遇到一个结点时要做的操作，先看看它是不是要找的结点，如果不是那么入vector
  if(pRoot == NULL)
    return false;
  if(pRoot == pNode && pRoot -> left == NULL && pRoot -> right == NULL)
    return true;
  path.push_back(pRoot);
  //如果该结点不是我们要找的，这里我们遍历左子树看看这个结点在左子树中
  bool found = getNodePath(pRoot -> left,pNode,path);
  //如果左子树中没有找到，再从右子树找
  if(!found)
    found = getNodePath(pRoot -> right,pNode,path);
  //如果右子树中也没找到，那么这个我们要找的结点不在pRoot及其子树中，我们要找的路径也不经过pRoot
  //于是就将pRoot踢出vector
  if(!found)
    path.pop_back();
  //这里返回一个值给调用该函数的上一层
  return found;
}
void getNodePath(BinaryTreeNode * pRoot,BinaryTreeNode * pNode){
  if(pRoot == NULL || pNode == NULL)
    return;
  vector<BinaryTreeNode*> path;
  if(getNodePath(pRoot,pNode,path)){
    vector<BinaryTreeNode*>::iterator iter = path.begin();
    while(iter != path.end())
      printf("%d ",*iter -> value);
  }
}