C++剑指offer(面试题55 - I. 二叉树的深度)【递归】

糖逗

题目描述：

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

 

提示：

节点总数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <malloc.h>


using namespace std;

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

TreeNode* Create(vector<int> input){
        TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
        for(int i= 0; i < input.size(); i++){
                res[i].val = input[i];
                res[i].left = NULL;
                res[i].right = NULL;
        }
        for(int i = 0; i < input.size()/2-1; i++){
                if(2*i+1 <= input.size()){
                        res[i].left = &res[2*i+1];
                }
                if(2*i+2 < input.size()){
                        res[i].right =  &res[2*i+2];
                }
        }
        return res;
}

int solution(TreeNode* root){

        if(root == NULL) return 0;
        return 1+max(solution(root->left), solution(root->right));

}

int main(void){
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        
        TreeNode*root = Create(input);
        
        int res = solution(root);
        cout << res << endl;
        return 0;
}

注意事项：
1.暂无。

糖逗