1. Binary Tree Preorder Traversal

Description

Given a binary tree, return the preorder traversal of its nodes' values. Example:
Input: [1,null,2,3] 1 2/3
Output: [1,2,3]

Analysis

실제는 두 갈래 나무의 순서가 두루 다니고 순서는 뿌리 노드에 대한 접근 순서가 되어야 한다..

leetcode 트리 노드의 정의는 다음과 같다

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

창고의 사상을 이용하여 뿌리 노드, 방문 값, 창고를 반환하고 좌우 하위 노드를 눌러 창고 꼭대기, 창고 꼭대기를 방문한다.창고가 비어 있을 때까지..

Solution

//  ， ， ， ， 。
//  ， 。
class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector result;
        stack s;
        if(root!=nullptr)
            s.push(root);
        while(!s.empty())
        {
            TreeNode* p = s.top();
            result.push_back(p->val);
            s.pop();
            if(p->right!=nullptr)
                s.push(p->right);
            if(p->left!=nullptr)
                s.push(p->left);
        }
        return result;
    }
};

2.Binary Tree Inorder Traversal

Description

Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3] 1 2/3
Output: [1,3,2]

Analysis

실제로는 두 갈래 나무의 중서가 두루 다닌다

왼쪽 노드가 없을 때까지 뿌리와 왼쪽 왼쪽을 끊임없이 눌러 넣는다

Solution

//  ， ， 。
class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack s;
        TreeNode* p = root;
        while(!s.empty() || p!=nullptr)
        {
            if(p!=nullptr)
            {
                s.push(p);
                p = p->left;
            }
            else
            {
                //  
                p = s.top();
                s.pop();
                result.push_back(p->val);
                //  
                p = p->right;
            }
        }
        return result;
        
    }
};

3.Binary Tree Postorder Traversal

Description

Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3] 1 2/3
Output: [3,2,1]

Analysis

두 갈래 나무가 뒤돌아다닌다

이 문제는 난이도가 있으니 우자수의 존재를 고려해야 한다

Solution

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector result;
        stack s;
        TreeNode *p=root, *q = nullptr;
        do
        {
            //  
            while(p!=nullptr)
            {
                s.push(p);
                p = p->left;
            }
            q = nullptr;
            while(!s.empty())
            {
                p = s.top();
                s.pop();
                //  ， ， 
                if(p->right == q)
                {
                    result.push_back(p->val);
                    //  
                    q = p;
                }
                //  ， ， ， 
                else
                {
                    s.push(p);
                    p = p->right;
                    break;
                }
            }
        }while(!s.empty());
        return result;
    }
};

총결산

두 갈래 나무의 세 가지 역행 방식은 두 갈래 나무 알고리즘의 전제 조건이다

두 갈래 나무의 세 가지 역행 방법이 가장 간단한 것은 역귀지 방식으로 다음과 같다

//  
void preorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        visit(root);
        preorder(root->left);
        preorder(root->right);
    }
}

//  
void inorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        inorder(root->left);
        visit(root);
        inorder(root->right);
    }
}

//  
void postorder(TreeNode *root)
{
    if(root!=nullptr)
    {
        postorder(root->left);
        postorder(root->right);
        visit(root);
    }
}

귀속 방식은 간단하기 때문에 창고나 단서 두 갈래 나무로 이 세 가지를 훑어보는 것을 배워야 한다.

4. Binary Tree Level Order Traversal

Description

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7], 3/ 9 20/ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ]

Analysis

두 갈래 나무의 층차 역주행, 층차 역주행은 두 갈래 나무의 넓이 우선 검색 방식이고 선후 중 역주행은 두 갈래 나무의 깊이 우선 검색 방식이다

하나의queue를 만들고 먼저 뿌리 노드를 넣는다. 이때 뿌리 노드의 좌우 두 개의 하위 노드를 찾고, 이때 뿌리 노드를 제거한다. 이때queue의 원소는 바로 다음 층의 모든 노드이다. 하나의for로 그것들을 순환한 다음에 1차원 벡터에 저장하고, 다 겪은 후에 이 1차원 벡터를 2차원 벡터에 저장한다. 이런 식으로 추측하면 층차를 완성할 수 있다

비교적 복잡한 것은 층수를 분리해야 한다는 것이다

class Solution {
public:
    vector > levelOrder(TreeNode *root) {
        vector > res;
        if (root == NULL) return res;
        //  
        queue q;
        //  
        q.push(root);
        while (!q.empty()) {
            //  
            vector oneLevel;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

5. Same Tree

Description

Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Analysis

두 갈래 나무가 같은지 아닌지를 판단하려면 반드시 나무 구조와 상응하는 노드 값이 같아야 한다..

나무의 구조가 같다. 바로 이 곳에 노드가 있는지, 이 곳에 노드가 없는지 비교하는 것이다

귀속된 생각을 채택하여 세 가지 상황으로 나눈다. 만약에 두 위치가 모두 비어 있다면 같고 하나가 비어 있지 않으면 다르다. 마지막 노드, 왼쪽 나무, 오른쪽 나무 세 가지 판단이 합쳐진다

Solution

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        //  ， 
        if(!p && !q)
            return true;
        //  
        if(!p || !q)
            return false;
        //  ， ， 
        return (p->val==q->val) && (isSameTree(p->left, q->left)) 
        && (isSameTree(p->right, q->right));
    }
};

6. Symmetric Tree

Decription

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Analysis

나무 한 그루가 대칭적인지 아닌지를 판단한다.사고방식은 두 나무가 같은지 아닌지를 판단하는 것과 유사하다.모두 돌아가는 사상이다. 차이점은 이곳은 나무이기 때문에 뿌리를 먼저 고려해야 한다는 것이다.뒤에 세 쪽이 합쳐진 곳에서 두 나무가 같다고 판단하는 것은 동시에 가식적이고 오른쪽이다.한 그루의 나무가 대칭적인지 아닌지를 판단하려면 좌우, 오른쪽 왼쪽으로 돌아가야 한다..

Solution

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        else
            return isSymmetric(root->left, root->right);
    }
    
    bool isSymmetric(TreeNode *p, TreeNode *q)
    {
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;
        return (p->val == q->val) && (isSymmetric(p->left, q->right)) 
        && (isSymmetric(p->right, q->left));
    }
};

7. Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Analysis

선차적 역주행과 중차적 역주행 결과에 따라 두 갈래 나무를 세운다

선순의 첫 번째 순서는 뿌리가 틀림없다. 그래서 원 두 갈래 나무의 뿌리 노드는 제목에서 매우 관건적인 조건을 주었다. 바로 나무에 같은 원소가 없다는 것이다. 이 조건이 있으면 우리는 중순 역순에서도 뿌리 노드의 위치를 정하고 뿌리 노드의 위치로 중순 역순을 좌우 두 부분으로 나누어 각각 원함수를 호출할 수 있다

Solution

class Solution {
public:
    TreeNode *buildTree(vector &preorder, vector &inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode *buildTree(vector &preorder, int pLeft, int pRight, vector &inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) return NULL;
        int i = 0;
        for (i = iLeft; i <= iRight; ++i) {
            if (preorder[pLeft] == inorder[i]) break;
        }
        TreeNode *cur = new TreeNode(preorder[pLeft]);
        cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);
        cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);
        return cur;
    }
};

8. Construct Binary Tree from Inorder and Postorder Traversal

Description

Given inorder and postorder traversal of a tree, construct the binary tree.

Analysis

중서와 후서를 이용하여 두 갈래 나무를 세운다

중서의 역행 순서는 좌-근-우이고 후서의 순서는 좌-우-근이며 이런 나무의 재건은 일반적으로 역귀로 이루어진다.후순의 마지막 순서는 뿌리가 틀림없기 때문에 원 두 갈래 나무의 뿌리 노드는 제목에서 매우 관건적인 조건을 주었다. 바로 나무에 같은 원소가 없다는 것이다. 이 조건이 있으면 우리는 중순 역행에서도 뿌리 노드의 위치를 정하고 뿌리 노드의 위치로 중순 역행을 좌우 두 부분으로 나누어 각각 원 함수를 호출할 수 있다

Solution

class Solution {
public:
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    TreeNode *buildTree(vector &inorder, int iLeft, int iRight, vector &postorder, int pLeft, int pRight) {
        if (iLeft > iRight || pLeft > pRight) return NULL;
        TreeNode *cur = new TreeNode(postorder[pRight]);
        int i = 0;
        for (i = iLeft; i < inorder.size(); ++i) {
            if (inorder[i] == cur->val) break;
        }
        cur->left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + i - iLeft - 1);
        cur->right = buildTree(inorder, i + 1, iRight, postorder, pLeft + i - iLeft, pRight - 1);
        return cur;
    }
};

총결산

두 갈래 나무는 일종의 귀속 데이터 구조로 기본적으로 모든 제목은 귀속 사상을 고려할 수 있다..

역귀는 반드시 DFS이고 두 갈래 나무의 선순 중순 후순은 모두 DFS로 볼 수 있다..

귀속과 교체의 차이

귀속은 중복 호출 함수 자체가 순환을 실현하는 것이다.교체는 함수 내의 어떤 단락 코드가 순환을 실현하는 것이다

귀속 순환 중 정지 조건을 충족시키는 상황이 발생하면 층층이 되돌아와 끝낸다.반복은 계수기를 사용하여 순환을 끝낸다.

귀속은 과정이나 함수에서 자신을 호출하는 것이다.귀속을 사용할 때, 반드시 명확한 귀속 종료 조건이 있어야 하는데, 이를 귀속 출구라고 부른다

교체는 점차적으로 가까워지고 새로운 값으로 낡은 값을 덮어쓰고 조건이 충족된 후에 끝날 때까지 중간 값을 저장하지 않아 공간 이용률이 높다.귀속은 하나의 문제를 약간 상대적으로 작은 문제로 분해하고 귀속 출구가 원래의 길로 되돌아오기 때문에 반드시 관련 중간 값을 저장해야 한다. 이런 중간 값은 창고에 눌러 저장하고 문제의 규모가 비교적 크면 대량의 메모리를 차지한다

9. Minimum Depth of Binary Tree

Description

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.

Analysis

한 그루의 나무의 최소 깊이, 즉 잎 노드의 깊이를 가장 빨리 찾는 것을 판단한다

귀속, 빈 트리에 0 반환하기;
왼쪽 트리가 비어 있으면 오른쪽 트리의 최소 깊이 +1을 되돌려줍니다.(1을 더하는 것은 뿌리를 덧붙여야 하기 때문이다. 아래와 같다)
오른쪽 트리가 비어 있으면 왼쪽 트리의 최소 깊이 +1을 되돌려줍니다.
좌우 트리가 비어 있지 않으면 왼쪽, 오른쪽 트리의 최소 깊이의 작은 값을 취하고 +1;

Solution

class Solution {
public:
    int minDepth(TreeNode* root) {
        //  ， brother
        return minDepth(root, false);
    }
    
    int minDepth(TreeNode* p, bool hasbrother)
    {
        //  
        if(!p)
            return hasbrother?INT_MAX:0;
        //  
        //  
        return 1+min(minDepth(p->left, p->right!=NULL), 
                    minDepth(p->right, p->left!=NULL));
        
    }
};

10. Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.

Analysis

다른 것을 고려할 필요가 없고 직접 귀속한다

Solution

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        else
            return 1+max(maxDepth(root->left), maxDepth(root->right));
        
    }
};