题目描述

题解1:直接对二叉树进行中序遍历

使用vector保存每条二叉树的路径长度,然后排序找到最长路径 或者使用大根数,保存每条二叉树的路径长度,然后弹出最长路径

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void inorder(TreeNode * root,priority_queue<int> &que,int count){
        if(!root){
            que.push(count);
            return;
        }
        count++;
        inorder(root->left, que, count);
        inorder(root->right,que, count);
        
    }
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot ==NULL) return 0;
        priority_queue<int> que;
        int count = 0;
        inorder(pRoot, que, count);
        return que.top();
    }
};

题解2:自底向上递归

当为节点为NULL时候,认为树的深度为0;没返回一层,深度加1.

即使对于空结点,它的深度为0,自底向上递归,即先递归到最底部,再逐步返回最优值至上层结点

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(!pRoot){
            return 0;
        }
        int leftdepth = TreeDepth(pRoot->left);
        int rightdepth= TreeDepth(pRoot->right);
        return max(leftdepth,rightdepth)+1;
    }
};