Binary tree (이진 트리)

1. 이진 트리 개념

• 트리는 계층적인(hierarchical) 트리 구조를 시뮬레이션하기 위한 자주 사용되는 데이터 구조임

• 최상위 노드는 root라 부름

• 트리는 노드로 구성되어 있고, 부모(parent), 자식(child) 노드로 구분됨

• 이진 트리에서 한 노드에 2개 자식 노드를 갖을 수 있음

• 노드 예시 그림
  

2. 트리 순회
   트리를 탐색하기 위해 3 가지 방법이 있다. 각 방법은 전/중/후위 순회이며 이를 구현하기 위해 recursive, iteratively하게 구현할 수 있다.
   (재귀적인 방법은 스텍오버 플로우에 취약하므로, 데이터가 많을 때 iteratively로 구현해야한다.)

• 전위 순회 (pre-order)
  1) recuresive와 2) iteratively 두 가지 방법 모두 time, space가 o(n)이 소요된다.
  1) recursive
  

2) iteratively

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        
        if(root==NULL)return res;
        
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* pre_node = st.top();
            res.push_back(pre_node->val);
            st.pop();
            if(pre_node->right)
            st.push(pre_node->right);
            if(pre_node->left)
            st.push(pre_node->left);
            
        }
        return res;
    }
};

• 중위 순회 (In-order)
  1) recursive
  

2) iteratively

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        
        stack<TreeNode *> st;
        TreeNode* pre_node = root;        
        while(!st.empty()||pre_node){
            if(pre_node){
                st.push(pre_node);
                pre_node= pre_node->left;
            }
            else{
                TreeNode* temp = st.top();
                res.push_back(temp->val);
                st.pop();
                pre_node=temp->right;
            }
        }
        return res;
    }

• 후위 순회 (Post-order)
  1) recursive
  

2) iteratively

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        
        if(!root) return res;
        
        stack<TreeNode *> st;
       TreeNode* pre_node=root;  
        TreeNode* last = NULL;
        
        while(!st.empty()||pre_node){
            if(pre_node){
                st.push(pre_node);
                pre_node=pre_node->left;
            }
            else{
                TreeNode* temp = st.top();
                if(temp->right&& last!= temp->right){
                    pre_node = temp->right;
                }
                else{
                	res.push_back(temp->val);
                    st.pop();
                    last = temp;
                    }
            }
            
        }
        return res;
    }

참고

• 재귀함수 장/단점: https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60
• 트리 개념 및 순회 방법: https://m.blog.naver.com/rlakk11/60159303809