之字形从上到下打印一棵二叉树

思路

• 通过2个栈交替保存当前行和它的下一行的数据
• 通过两个变量记录栈的当前索引和下个栈的索引
• 两个栈保存节点的顺序相反，一个是从左到右一个从右到左
• 思考栈先进后出的特点。

注意:

• 边界条件的处理

   void printFontNode(TreeNode*pRoot){
  
  if (pRoot == nullptr) {
      return;
  }
  std::stack<TreeNode*>pStacks[2];
  int current = 0;
  int next = 1;
  while (!pStacks[0].empty()||!pStacks[1].empty()) {
      TreeNode*pNode = pStacks[current].top();
      pStacks[current].pop();
      printf("%d",pNode->val);
      if (current == 0) {
          if (pNode->leftNode != nullptr) {
              pStacks[next].push(pNode->leftNode);
          }
          if (pNode->rightNode != nullptr) {
              pStacks[next].push(pNode->rightNode);
          }
      }else{
          if (pNode->rightNode != nullptr) {
              pStacks[next].push(pNode->rightNode);
          }
          if (pNode->leftNode != nullptr) {
              pStacks[next].push(pNode->leftNode);
          }
      }
      if (pStacks[current].empty()) {
          printf("\n");
          next = 1-next;
          current = 1-current;
      }
  }
  }
  

输入一个整数数组，判断它是不是一个二叉搜索树的后序遍历

• 先获取数组最后一个元素，二叉树的根节点元素
• 左面遍历直到元素大于根节点
• 右面接着遍历。如果元素小于根节点的元素，则不满足二叉搜索树。
• 然后再分别递归左右面的小的子树，看是否满足二叉搜索树

直接上代码

  //根据一个数组确认它是不是二叉搜索树的后序遍历
        bool verifySequenceOf(int sequence[],int length)
    {
    if (sequence == nullptr || length<=0) {
        return false;
    }
    //取出根节点
    int root = sequence[length-1];
    
    int i = 0;
    //遍历左子树。大于root说明到了右子树
    for (; i<length-1; ++i) {
        if (sequence[i]>root) {
            break;
        }
    }
    //遍历右子树。如果有小于根节点的则直接返回false
    int j = i;
    for (; j<length-1; j++) {
        if (sequence[j]<root) {
            return false;
        }
    }
    //递归左右自身的每个小组。看是否满足左面均小于根，右面均大于根
    bool left = true;
    if (i>0) {
        left = verifySequenceOfBST(sequence, i);
    }
    
    bool right = true;
    if (i<length - 1) {
        right = verifySequenceOfBST(sequence+i, length-1-i);
    }
    return left&&right;
}