104. [두 갈래 나무의 최대 깊이] Maximum Depth of Binary Tree

모자 zhzhC++dadasort>가장 기초적인 두 갈래 나무가 두루 다니는 문제로 최대 깊이를 구합니다.
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.

두 갈래 나무도 잊어버려서 약간의 근심이 있다

이 문제부터 도론의 내용을 처음 섭렵했다. 가장 기본적인 두 갈래 나무이자 가장 기본적인 역력이다.하지만 생각해 봐, 만약 이 문제가 없다면, 나는 영원히 잊어버릴 거야!대법을 두루 훑어보는 것이 생각나면 두 갈래 나무의 시체가 온 들에 널려 있는 것을 보아라.두 갈래 트리의 기초는 깊이 우선 검색, 폭 우선 검색, 최대/최소 깊이, 최대/최소 넓이를 포함하고 귀속과 관련된다.초보적인 느낌은 두 갈래 나무에 대해 이 몇 개를 파악하면 거의 충분하다.

돌아오다

매번 내가 돌아오는 것을 볼 때마다 조금은 보고 두려워한다.그러나 적어도 이 문제에 대해 말하자면 자신의 뇌 용량의 메모리와 CPU가 부족하여 귀속을 따라 심사숙고할 수는 없지만 귀속은 확실히 가장 쉽게'제6감'으로 문제를 해결하는 방법이다."어차피 내가 해결할 수 없는 건 내 아이가 해결하게 해줘"이게 귀속의 정수인 것 같아~

귀속으로 두 갈래 나무의 최대 깊이를 구하다

주석이 있는 코드를 보십시오 (오늘은 주석이 상세해서 @-@) 2016-07-18 00:04:10

/**
 * 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 maxDepth(TreeNode* root) {
        // ， 
        if(!root) return 0; //0 ， 。
        
        int leftdepth = maxDepth(root -> left) + 1;// 
        int rightdepth = maxDepth(root -> right) + 1;// 
        
        return max(leftdepth,rightdepth);// 
    }
};

운행 시간 8ms.더 빠른 방법이 있는 것 같습니다.

신기한 창고, 비귀속 방법

그 당시에 데이터 구조를 배웠고 선생님께도 많이 드렸다.결함이 있다.

창고, 나는 함부로 사용한 적이 없다

"이차 트리의 후차 반복 비귀환 알고리즘을 사용합니다. 후차 반복 비귀환 알고리즘은 하나의 창고를 사용하여 이루어지기 때문에 매번 한 경로에서 맨 밑바닥으로 올라가야만 접근할 수 있고 오른쪽으로 접근할 수 있습니다. 따라서 창고가 반복 중인 최대 값, 즉 두 갈래 트리의 최대 깊이를 기록합니다."
먼저 블로그원의 코드 학습 학습을 붙인다.

#include 
#include 
using namespace std;
typedef struct BinTree
{
    int data;
    BinTree *lc;
    BinTree *rc;
}BTNode,*BinTree;
int max(int a,int b)
{
    return (a>b)?a:b;
}

int BinTreeDepth(BinTree T)
{
    stack s;
    BinTree p = T,r = NULL;
    int depth=0;
    while(p||!s.empty())
    {
        if(p)
        {    // 
            s.push(p);
            int size = s.size();// 
            depth = max(depth,size);// 
            p = p->lc;
        }
        else
        {    // 
            p = s.top();
            if(p->rc&&p->rc!=r)// ， 
            {
                p = p->rc;
                s.push(p);
                int size = s.size();// 
                depth = max(depth,size);// 
                p = p->lc;
            }else
            {
                p=s.top();
                s.pop();
                cout<data<