求二叉树的深度递归与非递归版详解编程语言

当只有一个节点时，二叉树的深度为1，这与求二叉树的高度略微有点不同。

好像之前在leetcode上还是什么上写的代码，整理一下

#include<iostream> 
using namespace std; 
struct TreeNode { 
	    int val; 
	    TreeNode *left; 
	    TreeNode *right; 
	    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
}; 
	 
	class Solution { 
	public: 
		int maxDepth(TreeNode *root) { 
			// Start typing your C/C++ solution below 
			// DO NOT write int main() function 
			int depth; 
			if(root==NULL)return 0; 
			else{ 
				depth=(maxDepth(root->left)>maxDepth(root->right)? 
					maxDepth(root->left):maxDepth(root->right))+1; 
				return depth; 
 
			} 
 
		} 
	}; 
 
int main(){ 
	TreeNode n1(5); 
	TreeNode n2(6); 
	TreeNode n3(7); 
	TreeNode n4(8); 
	TreeNode n5(9); 
	TreeNode n6(10); 
	//n1.left=&n2; 
	n1.right=&n3; 
	n2.left=&n4; 
	n4.left=&n5; 
	//n5.right=&n6; 
 
	Solution s; 
	int dep=s.maxDepth(&n1); 
	cout<<dep<<endl; 
 
}

非递归版本，需保存每个节点的深度信息，自顶向下计算。所以定义了数据结构denode一方面保存节点的指针，一方面保存节点的深度值。

用队列来保存

struct TreeNode { 
    int val; 
    TreeNode *left; 
    TreeNode *right; 
     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
  }; 
  
 struct denode   
{   
    TreeNode* node;   
    int degree;   
};   
class Solution { 
public: 
    int maxDepth(TreeNode *root) { 
        // Start typing your C/C++ solution below 
        // DO NOT write int main() function 
      
    if(root==NULL)return 0;   
    queue<denode> que;   
       
    denode dnode;   
    dnode.degree=1;   
    dnode.node=root;   
   
    que.push(dnode);   
   
    int degree=1;   
    while(!que.empty())   
    {   
        denode ptr=que.front();   
        que.pop();   
   
        degree=ptr.degree;   
   
        if(ptr.node->left!=NULL)   
        {   
            denode p;   
            p.node=ptr.node->left;   
            p.degree=ptr.degree+1;   
            que.push(p);   
        }   
   
        if(ptr.node->right!=NULL)   
        {   
            denode p;   
            p.node=ptr.node->right;   
            p.degree=ptr.degree+1;   
            que.push(p);   
        }   
    }   
    return degree;    
         
    } 
};