104二叉树的最大深度

二叉树的最大深度

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。

解题思路：这一题想了三种解法，其中两种是递归解法。第一种递归是采用自顶向下，只要有孩子结点，深度就加一，然后和最大深度进行比较，选择是否更新。第二种递归是采用自底向上，走到叶节点的话，更新为0，然后向上走，深度+1。第三种是非递归解法，使用中序非递归，双栈，一个栈存结点，一个栈存当前结点对应的深度，每次弹出结点，弹出当前最大深度，然后和最大深度比较，选择是否更新。

法一： 自顶向下递归

class Solution { public: int max_layer=1; int maxDepth(TreeNode* root) { if(!root)return 0; count_depth(root,0); return max_layer; } void count_depth(TreeNode *p,int cur_layer){ if(p){ cur_layer++; count_depth(p->left,cur_layer); count_depth(p->right,cur_layer); } else{ max_layer=max(max_layer,cur_layer); } } };

法二自底向上，稍微难理解一点

class Solution { public: int maxDepth(TreeNode* root) { if(!root)return 0; int left_depth=maxDepth(root->left); int right_depth=maxDepth(root->right); return max(left_depth,right_depth)+1; } };

法三中序非递归

class Solution { public: int maxDepth(TreeNode* root) { if(!root)return 0; stack<TreeNode*>node; stack<int>depth; int max_layer,cur_layer; max_layer=cur_layer=1; TreeNode *p=root; while(p||!node.empty()){ while(p){ node.push(p); p=p->left; depth.push(cur_layer); cur_layer++; } p=node.top(); cur_layer=depth.top(); max_layer=max(max_layer,cur_layer); depth.pop(); node.pop(); cur_layer++; p=p->right; } return max_layer; } };