写在前面：涉及到树的算法中，最简单的算法就是利用递归，但是递归的系统开销比较大，并且栈容量不可控，作为算法练习，以下将全部利用非递归方法进行遍历。

---

1. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

解题思路：

int maxDepth(TreeNode* root) {
        if( nullptr == root) return 0;
        queue<TreeNode*> que;
        int levelNum = 1;
        int depth = 1;
        que.push(root);
        while(0 != que.size())
        {
            if( 0 == levelNum)
            {
                ++depth;
                levelNum = que.size();
            }
            TreeNode* ptr = que.front();
            if(ptr->left)
                que.push(ptr->left);
            if(ptr->right)
                que.push(ptr->right);
            que.pop();
            --levelNum;
        }
        return depth;
    }

---

2. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解题思路：二叉树离不开遍历，遍历分为前序遍历，中序遍历和后续遍历，记录之前的遍历信息，然后与当前遍历的节点相对比，二叉搜索树的中序遍历就是一个升序数组。

bool isValidBST(TreeNode* root) {
        if(nullptr == root)
            return true;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    TreeNode* pre = nullptr;
    st.push(root);
    while(st.size()!= 0||cur!=nullptr){
        if(nullptr != cur)
        {
            if( cur->left )
                st.push(cur->left);
            cur = cur->left;
        }
        else{
            cur = st.top();
            if(pre == nullptr)
                pre = cur;
            else if( pre->val >= cur->val)
                return false;
            else
                pre = cur;
            st.pop();
            if(cur->right)
                st.push(cur->right);
            cur = cur->right;
        }
    }
    return true;
   }

---

3. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

解题思路：系统递归的思想就是利用栈，此题也是可以构造两个栈，先将左右子树对应位置的元素压入栈，每次只需要取出栈顶的元素比较，如果相等，那么将栈1的子树以从左到右的顺序入栈，栈2的子树则以从右到左的顺序入栈才能保证栈顶的元素是镜像对应的。
抽象思想和递归法是一致的，从树中随意取出两个点a1,a2，保证这两个点在树中的结构是镜像对应的，如果a1==a2，那么它们子孩子的镜像对应关系就应该是 (a1->left,a2->right)(a1->right,a2->left)

bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        stack<TreeNode*> s1, s2;
        s1.push(root->left);
        s2.push(root->right);
        
        while (!s1.empty() && !s2.empty()) {
            TreeNode *node1 = s1.top();
            TreeNode *node2 = s2.top();
            s1.pop();
            s2.pop();
            if( !node1&&!node2 ) continue;
            if((node1 && !node2) || (!node1 && node2)) return false;
            if (node1->val != node2->val) return false;
            s1.push(node1->left);
            s1.push(node1->right);
            s2.push(node2->right);
            s2.push(node2->left);
        }
        return true;
}

---

4. 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
3
/
9 20
/
15 7
返回结果
[
[3],
[9,20],
[15,7]
]

解题思路：利用队列，记录以访问的点，由于队列是先进先出的功能，所以所有访问顺序全部保持这从左到右的顺序。由于返回结果需要输出成vector<vecter<int>>的形式，所以我们需要知道，每次层遍历结束的位置，我们可以设置一个标志位，记录每一层需要访问的个数，每访问一次，减1，当标志位==0时，插入到vector中这时队列中存在的个数就是下一层需要访问的个数。

vector<vector<int> > levelOrder(TreeNode* root){
      vector<vector<int>> rs;
      if( !root) return rs;
      queue<TreeNode*> que;
      que.push(root);
      int levelNo = 0;
      int levelNum = 1;
      rs.resize(1);
      while(!que.empty()){
          if(0 == levelNum){
              ++levelNo;
              levelNum = que.size();
              rs.resize(levelNo+1);
          }
          TreeNode* cur = que.front();
          rs[levelNo].push_back(cur->val);
          que.pop();
          --levelNum;
          if(cur->left) que.push(cur->left);
          if(cur->right) que.push(cur->right);

      }
      return rs;
  }

---

5. 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5

解题思路：实际上上这个有序数组就是这个二叉搜索树的中序遍历结果，根据二分查找的思想找到需要加入的点，以此类推即可。本题如果采用非递归算法，需要构造并记录每次的父节点和子节点的搜索范围，得不偿失，所以本题直接采用递归算法。

    TreeNode* construct(vector<int>& nums,int left,int right){        
        if(left > right )
            return nullptr;
        if( left == right ){
            TreeNode* root = new TreeNode(nums[left]);
            return root;
        }
        int rootIndex = (left+right)/2;
        TreeNode* root = new TreeNode(nums[rootIndex]);
        root->left = construct(nums,left,rootIndex-1);
        root->right = construct(nums,rootIndex+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty()) return nullptr;
        return construct(nums,0,nums.size()-1);
    }