LeetCode144. Preorder traversal of binary tree

Preorder traversal of two tree

1. problem

2. Ideas

1. First, let's introduce root first traversal — According to the root - Left son - The right son traverses the whole binary tree in order
2. Recursive method
3. Iterative method
Stack is not empty , One node per stack , Put it into the return array ！ After a node is out of the stack, its right and left children enter the stack （ In order ！）

3. Code implementation

（1） recursive

class Solution {
    
public:
    void PreOrder(TreeNode*cur,vector<int>& vec)
    {
    
        if(cur == NULL)return;
        vec.push_back(cur->val);// root   visit ！
        PreOrder(cur->left,vec);// Left  
        PreOrder(cur->right,vec);// Right  
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
    
           vector<int> result;
           PreOrder(root, result);
           return result;
    }
};

（2） iteration （ Utilization stack ）

// Put the linear stack of binary tree nodes 
class stack{
    
public:
	//1. initialization  
	void InitStack(){
    
		top = 0;
	}
	
	//2. Binary tree pointer stack  
	void Push(TreeNode *p){
    
		stack[top++] = p;
	}
	
	//3. Bomb stack  
    void Pop(){
    
        top--; 
    }
	
	//4. Sentenced to empty  
	bool Empty() {
    
  		if (top == 0)return true;
 		 return false;
    }
    
    //5. Take the top element of the stack  
    TreeNode* Top( ){
    
        return stack[top-1];
 }
private:
	int top;
	TreeNode *stack[512];
		
}; 

// Iterative method 
class Solution {
    
public:
    vector<int> preorderTraversal(TreeNode* root) {
    
    stack st;
    st.InitStack();// initialization  
    vector<int> result;
    
    if(root == NULL) return result;
   	st.Push(root);// The root node is in the stack ！
    while(!st.empty())// Stack is not empty  
    {
    
    	TreeNode* node = st.Top();// The pointer points to the top node of the stack  // in  
    	st.Pop();// Out of the stack  
        result.push_back(node->val);
    	if(node->right) st.Push(node->right);// The right son enters the stack ！( Empty nodes do not stack ) 
    	if(node->left)  st.Push(node->left);// Left son into the stack ！（ Empty nodes do not stack ） 
	}
	return result; // The stack is empty. , end  
	}
};