두 갈래 나무 밑바닥의 가장 왼쪽 원소를 찾아라

1749 단어

제목 설명


이것은 leetcode 위의 중간 알고리즘 문제입니다.https://leetcode.com/problems/find-bottom-left-tree-value/description/
설명은 다음과 같다. Given a binary tree,find the leftmost value in the last row of the tree.두 갈래 나무의 맨 밑에 있는 맨 왼쪽에 있는 원소의 값을 찾습니다.
예:
Input:
    1
   / \
  2   3
 /   / \
4   5   6
   /
  7

Output:
7

문제 풀이 사고방식


이 문제는 사실 두 갈래 나무의 깊이를 구하는 변형 문제다.나의 사고방식은 반복할 때 계수를 하고 한 노드에 접근할 때마다 level+1을 계산한 다음에 최대 깊이 depth를 현재 깊이 level과 비교한다. 만약에 depth가 level보다 작으면 현재 노드의 값을result에 부여한다.우리가 얻어야 할 것은 가장 왼쪽의 원소이기 때문에 먼저 왼쪽, 뒤에 오른쪽을 훑어보는 방법을 취하면 새로운 층을 훑어볼 때 첫 번째 훑어보는 노드는 반드시 가장 왼쪽의 노드가 될 것이다.

코드 구현


C++ 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int depth = 0;
        int result = root->val;
        visitNode(root, 0, depth, result);
    
        return result;
    }

    void visitNode(TreeNode* pNode, int level, int &depth, int& result) {
        level++;
        if (depth < level) {
            result = pNode->val;
            depth = level;
        }
    
        if (pNode->left) {
            visitNode(pNode->left, level, depth, result);
        }
        if (pNode->right) {
            visitNode(pNode->right, level, depth, result);
        }
    }
};

반성하다


나의visitNode 함수는 현재 깊이, 최대 깊이, 결과를 계산하는 데 사용되는 네 개의 인자를 전송했지만 너무 쓸데없는 느낌을 받았다.이후에 나는 반환값 방법이나while 순환을 통해 함수를 간소화하려고 시도할 것이다.만약 당신이 더 간결하고 효율적인 생각을 가지고 있다면 댓글에 메시지를 남길 수도 있고, 모두가 함께 토론하여 공부할 수도 있다.
체인식 두 갈래 나무의 생성
Ubuntu16.04에서 영어 키보드 사용 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage