//树节点定义
struct TreeNode{
int val;
TreeNode left
TreeNode right;
}

//递归前序遍历
void inorder(TreeNode *root){
if(!root) return;
cout << root->val;
inorder(TreeNode root->left);
inorder(TreeNode root->right);
}

//非递归的前序遍历
void preorder2(TreeNode root){
stack[HTML_REMOVED]s;
s.push(root);
while(!s.empty()){
TreeNodet = s.top();
s.pop();

    cout <<t->val <<' ';
    if(t->right) s.push(t->right);
    if(t->left) s.push(t->left);
}

}

//递归中序遍历
void inorder(TreeNode *root){
if(!root) return;
inorder(TreeNode root->left);
cout << root->val <<’ ‘;
inorder(TreeNode root->right);
}

//非递归中序遍历
void inorder2(TreeNode root){
stack[HTML_REMOVED]stk;
TreeNode cur = root;

while(cur || !stk.empty()){
    while(cur){
        stk.push(cur);
        cur = cur->left;
    }

    cur = stk.top();
    stk.pop();

    cout << cur->val <<' ';

    cur = cur->right;
}

}

//递归后序遍历
void postorder(TreeNode *root)
{
if(!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << ‘ ‘;
}

//层序遍历
void levelOrder(TreeNode root)
{
queue[HTML_REMOVED] q;
q.push(root);
while (!q.empty())
{
TreeNode t = q.front();
q.pop();

    cout << t->val << ' ';
    if (t->left) q.push(t->left);
    if (t->right) q.push(t->right);
}

}

//自下而上，自右向左的层序遍历

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

struct TreeNode
{
char val;
TreeNode left;
TreeNode right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(char x, TreeNode left, TreeNode right) : val(x),left(left), right(right) {}
};

void invertLevelOrder(TreeNode root)
{
queue[HTML_REMOVED] q;
stack[HTML_REMOVED] s;
q.push(root);
while (!q.empty())
{
TreeNode t = q.front();
q.pop();

    s.push(t);
    if (t->left) q.push(t->left);
    if (t->right) q.push(t->right);
}

while (s.size())
{
    cout << s.top()->val << ' ';
    s.pop();
}

}

int main()
{
TreeNode *root = new TreeNode(‘A’,
new TreeNode(‘B’,
new TreeNode(‘D’),
new TreeNode(‘E’)),
new TreeNode(‘C’));
invertLevelOrder(root);

return 0;

}

//递归求树高
int height(TreeNode *root){
if(!root) return;
return max(height(root->left),height(root->right)) + 1;
}

//非递归求树高
int height2(TreeNode root){
queue[HTML_REMOVED]q;
int height = 0;
q.push(root);
while(q.size()){
int n = q.size();
while(n–){
TreeNode t = q.front();
q.pop();
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
height++;
}
return height;
}

//二叉树按二叉链表形式存储
//写一个判别给定二叉树是否是完全二叉树的算法
bool isCompleteTree(TreeNode *root){
queue[HTML_REMOVED]q;
q.push(root);
bool leaf = false;

while(q.size()){
    TreeNode* t = q.front();
    q.pop();

    if(leaf && (t->left||t->right)) return false;
    if(!t->left && !t->right) leaf = true;
    if(!t->left && t->right) return false;

    if(t->left) q.push(t->left);
    if(t->right) q.push(t->right);
}
return true;

}

//计算二叉树所有双分支节点个数
int res;
void dfs(TreeNode* root){
if(!root) return;
if(root->left && root->right) res++;
dfs(root->left);
dfs(root->right);
}

//设树B是一棵采用链式结构存储的二叉树
//编写一个把树B中所有结点的左、右子树进行交换的函数。
void swapLeftRight(TreeNode* root){
if(root == nullptr) return;
swap(root->left,root->right);
swapLeftRight(root->left);
swapLeftRight(root->right);
}

//假设二叉树采用二叉链存储结构存储，设计一个算法
//求先序遍历序列中第 k(1≤k≤二叉树中结点个数)个结点的值
int res = 0,i = 0;
void dfs(TreeNode* root,int k){
i++;
if(i == k) res == root->val;
if(root->left) dfs(root->left);
if(root->right) dfs(root->right);
}

//已知二叉树以二叉链表存储，编写算法完成
//对于树中每个元素值为x的结点，删去以它为根的子树
void dfs(TreeNode* root,char x){
if(!root) return;
if(root->val == x)root = NULL;
if(root->left) dfs(root->left,x);
if(root->right) dfs(root->right,x);
}