三（简单题）、求一颗二叉树的深度

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

问题分析：递归遍历 

题目提供的节点：

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

解法【递归遍历】当遍历到叶子结点的时候，会自动返回+1操作，累计树的深度。

class Solution{
public:
        int TreeDepth(TreeNode* pRoot)
        {
            if(pRoot==nullptr)
                    return 0;
            int nleft=TreeNode(pRoot->left);
            int nright=TreeNode(pRoot->right);
            return(nleft>nright)?(nleft+1):(nright+1);//写为nleft++报错，改为++nleft正确
            /*换一种写法
            int TreeDepth(TreeNode  pRoot)
            {
            int nleft=TreeNode(pRoot.left);
            int nright=TreeNode(pRoot.right);
            //使用max函数必须包含算法头文件
            int Max=max(nleft,nright)+1;//不能直接return max()    Math.max属于JVS
            return Max;}
            */
        }
};

 

补充知识：为什么建议你用nullptr而不是NULL？

     C++中不能将void *类型的指针隐式转换成其他指针类型。

     NULL是0   在c++11中引入nullptr是空指针void，nullptr并非整型类别，甚至也不是指针类型，但是能转换成任意指针类型。

c++中 . 和 -> 的区别是什么？

A.B  A为对象或者结构体

A->B A为指针，->为成员提取，A->B是提取A中的成员B，A只能是指向类、结构、联合的指针；

：：是作用域运算符，A::B表示作用域A中的名称B，A可以是命名空间，类，结构

    1)类作用域操作符。“::”指明了成员函数所属的类。
     2)表示引用成员函数及变量，作用域成员运算符。例如：System::Math::Sqrt() 相当于System.Math.Sqrt()

：表示继承，另一种是构造函数

class Client:public: Allocatable{ }  //表示类Client继承自Allocatable

其实冒号后的内容是初始化成员列表，一般有三种情况：
1、对含有对象成员的对象进行初始化，例如，
类line有两个私有对象成员startpoint、endpoint,line的构造函数写成：
line（int sx,int sy,int ex,int ey）：startpoint（sx,sy），endpoint（ex,ey）{……}
初始化时按照类定义中对象成员的顺序分别调用各自对象的构造函数，再执行自己的构造函数
2、对于不含对象成员的对象，初始化时也可以套用上面的格式，例如，
类rectangle有两个数据成员length、width,其构造函数写成：
rectangle（）：length（1），width（2）{}
rectangle（int x,int y）：length（x），width（y）{}
3、对父类进行初始化，例如，
CDlgCalcDlg的父类是MFC类CDialog,其构造函数写为：
CDlgCalcDlg（CWnd* pParent ）： CDialog（CDlgCalcDlg::IDD, pParent）
其中IDD是一个枚举元素，标志对话框模板的ID
使用初始化成员列表对对象进行初始化，有时是必须的，有时是出于提高效率的考虑

完整代码如下：

#include<iostream>
using namespace  std;
int arr[7] = { 8,5,15,3,7,16,6 };
struct BinaryTree
{
	int data;
	BinaryTree *pLeft;
	BinaryTree *pRight;
};
BinaryTree *pRoot = NULL;
void InsertTree(BinaryTree *root,int data)
{
	if (root->data>data)//插入左边root->data>data等价于root->data=data;
	{
		if (root->pLeft == NULL)
		{
			root->pLeft = new BinaryTree;
			root->pLeft->data = data;
			root->pLeft->pLeft = root->pLeft->pRight = NULL;
		}
		else
		{
			InsertTree(root->pLeft, data);// 继续查找插入位置；
		}
	}
	else
	{
		if (root->pRight == NULL)
		{
			root->pRight = new BinaryTree;
			root->pRight->data = data;
			root->pRight->pLeft = root->pRight->pRight = NULL;
		}
		else
			InsertTree(root->pRight, data);

	}

}
void CreateTree(BinaryTree **root, int *array, int length)
{
	for (int i = 0; i < length; i++)
	{
		if (*root == NULL)//根节点
		{
			BinaryTree *temp = new BinaryTree;
			temp->data = arr[i];
			temp->pLeft = temp->pRight = NULL;
			*root = temp;
		}
		else
			InsertTree(*root, array[i]);
	}
}
void PreOrder(BinaryTree *tree)
{
	if (tree != NULL)
	{
		cout << tree->data << " ";
		PreOrder(tree->pLeft);
		PreOrder(tree->pRight);
	}
}
int TreeDepth(BinaryTree *root)
{
	if (root = NULL)
		return 0;
	int left = TreeDepth(root->pLeft);
	int right = TreeDepth(root->pRight);
	return(left > right) ? (left+1) : (right+1);
}
int main()
{
	int depth = 0;
	CreateTree(&pRoot, arr, 7);
	cout << "PreOrder：";
	PreOrder(pRoot);
	cout << endl;
	depth=TreeDepth(pRoot);
	cout << "Depth_Max:" << depth << endl;

	return 0;
}