반응형

이진트리에 해당하는 글 1

반응형

[Leetcode] 101. Symmetric Tree

Algorithm|2021. 8. 3. 17:04
반응형

Identifying the Problem

트리를 반으로 나눴을 때 대칭이 되는지 판단해 true, false를 return 한다.

단, 이런 경우는 대칭이 아니다

Organizing thoughts

1. 자녀 계층 왼쪽과 오른쪽으로 나눠 시작한다.

1-1 왼쪽은 중위 순회를 왼쪽 우선, 오른쪽은 오른쪽 우선으로 탐색한다.

2. 둘 중 하나 null 이면 flag = false

3. 탐색 중 둘 다 값이 다르면 flag = false  

Sourcecode

void answer(struct TreeNode *l,struct TreeNode *r,int *f);

bool isSymmetric(struct TreeNode* root){
    
    struct TreeNode *l,*r;
    
    l = root->left;
    r = root->right;
    
    int flag = 1;
    answer(l,r,&flag);
    
    return flag;
}


void answer(struct TreeNode *l,struct TreeNode *r,int *f)
{


    if(!l && r) *f = 0;
    if(l && !r) *f = 0;
    
    else if(l && r)
    {
      if(l->val != r->val) *f = 0;
      answer(l->left,r->right,f);
      answer(l->right,r->left,f);

    }

}

Mistake

  • return 값을 true로 한 경우와 false로 한 경우 코드가 꼬여서 복잡해지거나 에러가 난다.
    바로 true false로 하는 게 아니라 false 인 경우에만 flag를 세우는 방식으로 하니 이해가 편했다. 

 

반응형

'Algorithm' 카테고리의 다른 글

[Leetcode] 153. Find Minimum in Rotated Sorted Array  (0) 2021.08.04
[Leetcode] 206. Reverse Linked List  (0) 2021.08.03
[Leetcode] 100. Same Tree  (0) 2021.08.03
[Leetcode] 94. Binary Tree Inorder Traversal  (0) 2021.08.03
[Leetcode] 69. Sqrt(x)  (0) 2021.08.03

댓글()