之字形從上到下打印一棵二叉樹

思路

• 通過2個棧交替保存當前行和它的下一行的數(shù)據(jù)
• 通過兩個變量記錄棧的當前索引和下個棧的索引
• 兩個棧保存節(jié)點的順序相反，一個是從左到右一個從右到左
• 思考棧先進后出的特點。

注意:

• 邊界條件的處理

   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;
      }
  }
  }
  

輸入一個整數(shù)數(shù)組，判斷它是不是一個二叉搜索樹的后序遍歷

• 先獲取數(shù)組最后一個元素，二叉樹的根節(jié)點元素
• 左面遍歷直到元素大于根節(jié)點
• 右面接著遍歷。如果元素小于根節(jié)點的元素，則不滿足二叉搜索樹。
• 然后再分別遞歸左右面的小的子樹，看是否滿足二叉搜索樹

直接上代碼

  //根據(jù)一個數(shù)組確認它是不是二叉搜索樹的后序遍歷
        bool verifySequenceOf(int sequence[],int length)
    {
    if (sequence == nullptr || length<=0) {
        return false;
    }
    //取出根節(jié)點
    int root = sequence[length-1];
    
    int i = 0;
    //遍歷左子樹。大于root說明到了右子樹
    for (; i<length-1; ++i) {
        if (sequence[i]>root) {
            break;
        }
    }
    //遍歷右子樹。如果有小于根節(jié)點的則直接返回false
    int j = i;
    for (; j<length-1; j++) {
        if (sequence[j]<root) {
            return false;
        }
    }
    //遞歸左右自身的每個小組?？词欠駶M足左面均小于根，右面均大于根
    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;
}