基础算法与数据结构（二） 树（1）基础二叉树

//tree
 struct normalTreeNode {
      int val;
      TreeNode* sons[];
  };
//binary tree
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

	//递归
	vector<int> route;
 	void PreOrderTraversal(TreeNode* root){
		if(!root){
			route.push_back(root->val);
			PreOrderTraversal(root->left);
			PreOrderTraversal(root->right);
		}
	}

	//非递归
	vector<int> PreOrderTraversal(TreeNode* root){
		vector<int> route;
		stack<TreeNode*> s;
		TreeNode* cur = root;
		while(cur || s.empty()){
			while(cur){
				route.push_back(cur->val);
				s.push(cur);
				//go to the most left
				cur = cur->left;
			}
			if(!s.empty()){
				cur = s.top();
				s.pop();
				//back to right
				cur = cur->right;
			}
		}
		return route;
	}

	//递归
	vector<int> route;
 	void InOrderTraversal(TreeNode* root){
		if(!root){
			InOrderTraversal(root->left);
			route.push_back(root->val);
			InOrderTraversal(root->right);
		}
	}

	//非递归
	vector<int> InOrderTraversal(TreeNode* root){
		vector<int> route;
		stack<TreeNode*> s;
		TreeNode* cur = root;
		while(cur || s.empty()){
			while(cur){
				s.push(cur);
				//go to the most left
				cur = cur->left;
			}
			if(!s.empty()){
				cur = s.top();
				s.pop();
				route.push_back(cur->val);
				//back to right
				cur = cur->right;
			}
		}
		return route;
	}

	//递归
	vector<int> route;
 	void PostOrderTraversal(TreeNode* root){
		if(!root){
			PostOrderTraversal(root->left);
			PostOrderTraversal(root->right);
			route.push_back(root->val);
		}
	}

	//非递归
	vector<int> PostOrderTraversal(TreeNode* root){
		 stack<TreeNode> s;
       vector<int> ans;
        TreeNode* pre,cur;
        pre = NULL;
        if(root == NULL) return ans;
        s.push(root);
        while(!s.empty()){
            cur = s.top();
			//要么左右均为空，那么就是叶子节点放入route，或者前一个是左结点或者右结点回溯回来的，此时也是已经访问过左右放入父节点
            if((!cur->left&&!cur->right) || (pre && (pre == cur->left || pre == cur->right))){
                s.pop();
                ans.push_back(cur.val);
                pre = cur;
            }else{
				//向栈内先放右，再放左，先进后出
                if(cur->right) s.push(cur->right);
                if(cur->left) s.push(cur->left);
            }
        }
        return ans;
	}

TreeNode* invertTree(TreeNode* root) {
       if(root==NULL) return NULL;
       root->left = invertTree(root->left);
       root->right = invertTree(root->right);

       TreeNode* tmp = root->left;
       root->left = root->right;
       root->right = tmp;
       return root;
    }

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder){
        if(preorder.empty() || inorder.empty()) return NULL;
        TreeNode* root = new TreeNode(preorder[0]);
        if(preorder.size()==1 && inorder.size()==1) return root;
        int inOrderNum = FindNode(inorder,preorder[0]);
        vector<int> a(preorder.begin()+1,preorder.begin()+inOrderNum+1);
        vector<int> b(inorder.begin(),inorder.begin()+inOrderNum+1);
        vector<int> c(preorder.begin()+inOrderNum+1,preorder.end());
        vector<int> d(inorder.begin()+inOrderNum+1,inorder.end());
        root->left = buildTree(a,b);
        root->right = buildTree(c,d);
        return root;
    }

    int FindNode(vector<int> &v,int target){
        int size = v.size();
        for(int i=0;i<size;i++){
            if(v[i] == target) return i;
        }
        return -1;
    }