利用栈容器可以实现二叉树的非递归遍历

首先将每个节点都设置一个标志，默认标志为假，根据节点的的状态进行如下流程。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"seqstack.h"

//树的节点类型
typedef struct  node
{
	int flag;
	//数据域
	char ch;
	//指针域
	struct  node *lchild;
	struct  node *rchild;

}NODE;
int main()
{
	NODE nodeA = { 0,'A',NULL,NULL };
	NODE nodeB = { 0,'B',NULL,NULL };
	NODE nodeC = { 0,'C',NULL,NULL };
	NODE nodeD = { 0,'D',NULL,NULL };
	NODE nodeE = { 0,'E',NULL,NULL };
	NODE nodeF = { 0,'F',NULL,NULL };
	NODE nodeG = {0, 'G',NULL,NULL };
	NODE nodeH = {0, 'H',NULL,NULL };

	//建立关系
	nodeA.lchild = &nodeB;
	nodeA.rchild = &nodeF;

	nodeB.rchild = &nodeC;

	nodeC.lchild = &nodeD;
	nodeC.rchild = &nodeE;

	nodeF.rchild = &nodeG;
	nodeG.lchild = &nodeH;

	//初始化栈 (手动实现的栈)
	SeqStack stack = Init_seqstack();
	Push_SeqStack(stack,&nodeA);
	while ( !IsEmpty_SeqStack(stack))
	{
		NODE *top = (NODE *)GetTop_SeqStack(stack);
		Pop_SeqStack(stack);
		if (top->flag == 1)
		{
			printf("%c ",top->ch);
			continue;
		}
		top->flag = 1;
		if(top->rchild != NULL)
			Push_SeqStack(stack,top->rchild);
		Push_SeqStack(stack,top);
		if (top->lchild != NULL)
			Push_SeqStack(stack,top->lchild);
	}
	system("pause");
	return 0;
}

将代码稍作修改应用于LeetCode中的前中后非递归遍历二叉树
94 144 145(题号)

执行结果：通过显示详情
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了90.71%的用户

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        example(root, v);
        return v;
    }
 
    void example(TreeNode *root, vector<int> &path){
        stack<pair<TreeNode *, bool>> s;
        s.push(make_pair(root, false));
        bool flag;
        while(!s.empty()) 
        {
            root = s.top().first;
            flag = s.top().second;
            s.pop();
            if(root == NULL)
                continue;
            if(flag)
                path.push_back(root->val);
            else 
            {
            		//调整插入顺序即先中后序遍历 比如这里是后序遍历 按照后序遍历的左右根反着插入即可 依次类推
                    s.push(make_pair(root, true));
                    s.push(make_pair(root->right, false));
                    s.push(make_pair(root->left, false));
            }
        }
    }
};

递归遍历，深度以及叶子节点数量求解

typedef struct _PTNode{
char ch;
struct _PTNode* lchild;
struct _PTNode* rchild;
}PTNode;
//递归遍历
void RecursionBiTree(PTNode* root){
if (root == NULL){
return; }
//printf("%c", root->ch); //先序遍历
RecursionBiTree(root->lchild);
printf("%c", root->ch); //中序遍历
RecursionBiTree(root->rchild);
//printf("%c", root->ch); //后序遍历
}

//求叶子结点数量
int leafNum = 0;
void RecursionBiTree(PTNode* root){
if (root == NULL){
return; }
if (!root->lchild && !root->rchild){
leafNum++;
}
RecursionLeafNumTree(root->lchild);
RecursionLeafNumTree(root->rchild);
}

//求二叉树深度
int RecursionTreeDepth(PTNode* root){
int depth = 0;
if (root == NULL){
return depth;
}
int ldepth = RecursionTreeDepth(root->lchild);
int rdepth = RecursionTreeDepth(root->rchild);
depth = ldepth >= rdepth ? ldepth + 1 : rdepth + 1;
return depth;
}