左叶子之和

知我者，谓我心忧；不知我者，谓我何求

• 题目
• 思路
• 双指针
• 单指针
• 迭代
• 运行结果

给定二叉树的根节点 root ，返回所有左叶子之和。

输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

其实就是遍历一个树 设置一个变量 若是左叶子累加即可 左叶子的特点是什么 是上一个结点的左孩子，并且这个结点没有左右子树，所以是不是可以想到使用双指针的方式
接下来写出代码

一遍过 不要问怎么做到一遍过的， 问就是天赋

#include
#define ElemType int
using namespace std;
typedef struct BiNTree{
	struct BiNTree* Lchild;
	ElemType data;
	struct BiNTree* Rchild;
}BiNTree;
 
vector result;
void Creat(BiNTree* &T){
	int val;
	BiNTree* cur;//定义一个cur 
	queue Q;
	queue TreeQue;
	cout<<"请输入层序遍历的序列"<
		cout<<"树为空"< 
		T=(BiNTree*)malloc(sizeof(BiNTree));
		T->data=Q.front(); 
		TreeQue.push(T);
	}
	Q.pop();
	while(!Q.empty()){//我们每一次处理 处理的都是左右孩子，所以也就需要两个if
		cur=TreeQue.front();//取出此时树队中的第一元素
		if(Q.front()==-1){//此时这个结点值为NULL  
			cout<data<<"左孩子为空"<Lchild=NULL; 
		}
		else{//新生成一个树结点用来存放此时的结点信息 
			cout<data<<"左孩子为"<Lchild=(BiNTree*)malloc(sizeof(BiNTree)) ;
			cur->Lchild->data=Q.front();
			TreeQue.push(cur->Lchild);
		}
		Q.pop();//处理完数据之后需要弹出 来取此结点右子树的值 
		//上面的if  else 是处理结点左孩子  下面我们来处理右孩子 
		if(Q.front()==-1){
			cout<data<<"右孩子为空"<Rchild=NULL;
		} 
		else{
			cout<data<<"右孩子为"<Rchild=(BiNTree*)malloc(sizeof(BiNTree));
			cur->Rchild->data=Q.front();
			TreeQue.push(cur->Rchild); 
		}
		Q.pop();
		TreeQue.pop();
	}
} 

//使用双指针要特别注意根节点 要拿出来讨论 
void Deal(BiNTree* T,BiNTree* pre,int &sum){
	if(T->Lchild==NULL&&T->Rchild==NULL){
		if(pre->Lchild==T){
			sum+=T->data;
		}
		return;		
	}
	if(T->Lchild){
		Deal(T->Lchild,T,sum);
	} 
	if(T->Rchild){
		Deal(T->Rchild,T,sum);
	}
}
main(){
	BiNTree* T=NULL;int sum=0;
	Creat(T); 
	Deal(T,T,sum);	
	cout<<"此时的左叶子是"< 
单指针 
不会双指针怎么办，我们就使用最简单的递归 这里使用什么遍历方式呢？这里认为使用后序，这样左子树加右子树 不是美滋滋，但是若是没有左子树 或者右子树 又该怎么办？这就是递归到什么时候return的问题 之前我们有到叶子结点停 也有到NULL停 还有一个问题就是 怎么看与父节点的关系 若是到达叶子结点 返回一个0 作为标志 给上一层 若是上一层接受到的就是零 有时此时结点的左孩子 也就可以加 使用这里认为依然是叶子 返回 简单一句话 通过返回值来判断与父节点之间的关系
 
#include
#define ElemType int
using namespace std;
typedef struct BiNTree{
	struct BiNTree* Lchild;
	ElemType data;
	struct BiNTree* Rchild;
}BiNTree;
 
vector result;
void Creat(BiNTree* &T){
	int val;
	BiNTree* cur;//定义一个cur 
	queue Q;
	queue TreeQue;
	cout<<"请输入层序遍历的序列"<
		cout<<"树为空"< 
		T=(BiNTree*)malloc(sizeof(BiNTree));
		T->data=Q.front(); 
		TreeQue.push(T);
	}
	Q.pop();
	while(!Q.empty()){//我们每一次处理 处理的都是左右孩子，所以也就需要两个if
		cur=TreeQue.front();//取出此时树队中的第一元素
		if(Q.front()==-1){//此时这个结点值为NULL  
			cout<data<<"左孩子为空"<Lchild=NULL; 
		}
		else{//新生成一个树结点用来存放此时的结点信息 
			cout<data<<"左孩子为"<Lchild=(BiNTree*)malloc(sizeof(BiNTree)) ;
			cur->Lchild->data=Q.front();
			TreeQue.push(cur->Lchild);
		}
		Q.pop();//处理完数据之后需要弹出 来取此结点右子树的值 
		//上面的if  else 是处理结点左孩子  下面我们来处理右孩子 
		if(Q.front()==-1){
			cout<data<<"右孩子为空"<Rchild=NULL;
		} 
		else{
			cout<data<<"右孩子为"<Rchild=(BiNTree*)malloc(sizeof(BiNTree));
			cur->Rchild->data=Q.front();
			TreeQue.push(cur->Rchild); 
		}
		Q.pop();
		TreeQue.pop();
	}
} 

//使用双指针要特别注意根节点 要拿出来讨论 
int PostOrder(BiNTree* T,int &sum){
	if(T->Lchild==NULL&&T->Rchild==NULL){
		return 0;//此时的零作为一种达到叶子的标志	
	}
	if(T->Lchild){
		if(PostOrder(T->Lchild,sum)==0){
			//说明T的左孩子就是等于叶子结点
			sum+=T->Lchild->data; 
		}
	} 
	if(T->Rchild){
		//右孩子返回的是不是0都无所谓 因为下一个结点只可能是此结点的右孩子 
		PostOrder(T->Rchild,sum);
	}
}
main(){
	BiNTree* T=NULL;int sum=0;
	Creat(T); 
	PostOrder(T,sum);	
	cout<<"此时的左叶子是"< 
迭代 
这里也提供一个迭代版本吧 迭代版本最好理解这题 遍历每一个结点 若是满足左叶子的定义 直接累加即可 在这里写一种 其他都一样的条件累加即可
 
#include
#define ElemType int
using namespace std;
typedef struct BiNTree{
	struct BiNTree* Lchild;
	ElemType data;
	struct BiNTree* Rchild;
}BiNTree;
 
vector result;
void Creat(BiNTree* &T){
	int val;
	BiNTree* cur;//定义一个cur 
	queue Q;
	queue TreeQue;
	cout<<"请输入层序遍历的序列"<
		cout<<"树为空"< 
		T=(BiNTree*)malloc(sizeof(BiNTree));
		T->data=Q.front(); 
		TreeQue.push(T);
	}
	Q.pop();
	while(!Q.empty()){//我们每一次处理 处理的都是左右孩子，所以也就需要两个if
		cur=TreeQue.front();//取出此时树队中的第一元素
		if(Q.front()==-1){//此时这个结点值为NULL  
			cout<data<<"左孩子为空"<Lchild=NULL; 
		}
		else{//新生成一个树结点用来存放此时的结点信息 
			cout<data<<"左孩子为"<Lchild=(BiNTree*)malloc(sizeof(BiNTree)) ;
			cur->Lchild->data=Q.front();
			TreeQue.push(cur->Lchild);
		}
		Q.pop();//处理完数据之后需要弹出 来取此结点右子树的值 
		//上面的if  else 是处理结点左孩子  下面我们来处理右孩子 
		if(Q.front()==-1){
			cout<data<<"右孩子为空"<Rchild=NULL;
		} 
		else{
			cout<data<<"右孩子为"<Rchild=(BiNTree*)malloc(sizeof(BiNTree));
			cur->Rchild->data=Q.front();
			TreeQue.push(cur->Rchild); 
		}
		Q.pop();
		TreeQue.pop();
	}
} 
int LevelOrder(BiNTree* T){//这里我们是使用的是队列来完成这个操作
	queue Q; BiNTree* cur;int sum;
	if(T==NULL){//跟前面一样  若是为空则不需要进队  直接返回即可 
		return 0;; 
	}
	Q.push(T); 
	while(!Q.empty()){
		int size=Q.size();//需要一个值来保存 因为Q.size 是一直变得 
		for(int i=0;i
			cur=Q.front();
			if(cur->Lchild&&cur->Lchild->Lchild==NULL&&cur->Lchild->Rchild==NULL){//当前结点有左孩子 左左孩子是叶子结点 
				cout<<"找到此时左结点"<Lchild->data<Lchild->data;
			}
			if(cur->Lchild) Q.push(cur->Lchild);
			if(cur->Rchild) Q.push(cur->Rchild); 
			Q.pop();
		}
	}
	return sum;
} 
main(){
	BiNTree* T=NULL;int sum=0;
	Creat(T); 	
	cout<<"此时的左叶子之和是"< 
运行结果