tree traversal iteratively

• In order: 
• using stack
• Pre order: 
• only check stack.top() 的right child, not left child. 
• 
  
• Post order:  3 possibilities when doing traversal 

• traversing up the tree from the right
• traversing up the tree from the left
• traversing down the tree
• Can be used to get the max depth of a tree, without changing the tree structure

越是真正的牛人，胸怀就越是宽广。

   

第一个回复的人leinad根本没看清题目，却很自以为事的认为1337说错了。下面的人都为1337 鸣不平，我看了也觉得leinad有够蠢有够丢人。但是1337却是这么回复的  

要想真正成为牛人，就要放低姿态，接受大家的意见，努力欣赏他人，无论他们的想法看起来有多trivial，因为自己也曾经经历过那样的过程，才会得到现在的理解。

Determine if a Binary Tree is a Binary Search Tree (BST) Brute force：

 3 properties:
1) left tree is BST, right tree is BST ;
2) root is smaller than all the elements in right tree
3) root is larger than all the elements in left tree 一开始想了这个方法



这样是错误的，不应该suppose 左树的最小是最左边的点

所以正确的brute force solution

 
bool isSubTreeLess(node *p,int val){
    if(p==NULL)
         return 1;
    else {
      return (p->dataleft,val)&&isSubtree(p->right,val);
    }
} 

bool isSubTreeLarge(node *p,int val){
    if(p==NULL)
         return 1;
    else {
      return (p->data>val)&&isSubTree(p->left,val)&&isSubtree(p->right,val);
    }
} 

bool isBST(node *root){
     if (!p) return true;
     return isTreeLess(p->left,root->data)&&isTreeLarge(p->right,root->data)&&isBST(root->left)&&isBST(root->right);
}

/////////////**********/////////////

isBST(node *p,int min,int max){
if(p->datadata>max){

       return (isBST(p->left,min,p->data)&&isBST(p->right,p->data,max);
}
else return 0;
}

isBST(node *root){
   return isBST(root,INT_MIN,INT_MAX);
}

/////////////**********/////////////
inorder traversal

function test() : String
{
 return 10;
}