二叉树

struct node {
    int left;
    int right;
    int val;
}

什么是二叉数呢?

不能形成环.

二叉数的遍历

二叉树的先序、中序、后序遍历

先序：根左右

中序：左根右

后序：左右根

思考：给定一个数写出遍历方式

代码题1：递归遍历二叉树

1. 递归序、先序、中序、后序
2. 对任意一个点都会来到三次（自己画一个图理解）
3. head 会到三次（刚进来的时候、去左树回来、去右树回来)。
4. 第一次到达的数就是先序、第二次到打的数就是中序、第三次到达的数就是后序。
5. 这是在树上做动态规划的基础。

代码题2：非递归遍历二叉树实现二叉树的先序、中序、后序遍历（面试常考）

1. 任何递归函数都可以改成非递归。

2. 自己设计压栈来实现。

3. 建议记住流程强行记住就可以了。

4. 先序
   先序遍历： 入栈顺序头右r左l
   【0】先把头节点head 入栈。
   【1】栈不为空，弹出就打印
   【2】有右孩子压栈右边孩子，有左孩子就压栈左孩子

5. 后序—>可以用一个栈排序(先这样，提高coding)

后序遍历：入栈顺序头右r左l 出栈就是左右根
【0】先把头节点head 入栈。 申请两个stack。
【1】栈不为空，弹出就打印
【2】有左孩子压栈左边孩子，有右孩子就压栈右孩子
【3】逆序就是左右根、打印时候放栈中去。

1. 中序
   中序遍历： 牛逼！
   【1】整条左边界依次入栈。
   【2】无法入栈时，弹出节点、来到弹出节点的右边界执 行条件1.

代码题3：二叉树按层遍历

1. 宽度优先遍历，用队列
2. 可以通过设置flag变量的方式 ，来发现某一层的结束。

代码题4：二叉树最大宽度（经典面试题）

一、使用Map方式
二、不使用Map 使用几个变量

https://leetcode-cn.com/problems/maximum-width-of-binary-tree/

public static int maxWidthUseMap(Node head) {
                if (head == null) {
                    return 0;
                }
                Queue<Node> queue = new LinkedList<>();
                queue.add(head);

                // key 在 哪一层，value
                HashMap<Node, Integer> levelMap = new HashMap<>();
                levelMap.put(head, 1); // 头结点进队列我当然知道head在第一层

                int curLevel = 1; // 当前你正在统计哪一层的宽度
                int curLevelNodes = 0; // 当前层(curLevel层)，宽度目前是多少
                // 为什么是0？ 一个结点出来的时候把当前层结点++
                // 进去时候不统计，出来时候加到当前层的宽度上
                int max = 0; // 更新所有层的最大值
                while (!queue.isEmpty()) {
                        // 相当于 宽度优先
                        Node cur = queue.poll();
                        int curNodeLevel = levelMap.get(cur);
                        if (cur.left != null) { // 左孩子
                                levelMap.put(cur.left, curNodeLevel + 1);
                                queue.add(cur.left);
                        }
                        if (cur.right != null) {
                                levelMap.put(cur.right, curNodeLevel + 1);
                                queue.add(cur.right);
                        }
                        // 上面是宽度优先遍历

                        //
                        if (curNodeLevel == curLevel) {
                                curLevelNodes++;
                        } else {
                                // 当新层开始是 
                                max = Math.max(max, curLevelNodes);
                                curLevel++;
                                curLevelNodes = 1; 
                        }
                }
                max = Math.max(max, curLevelNodes); // 最后层
                return max;
        }

代码题5：二叉树序列化和反序列化

1. 很简单
2. 按层序列化

#include <iostream>
#include <stack>
#include <queue>
#include <cstdio>
// https://blog.csdn.net/Hairy_Monsters/article/details/82053541
using namespace std;

struct Node
{
   int value;
   Node *left;
   Node *right;
   Node(int x):value(x),left(NULL),right(NULL){}
};


void pre_traversal(Node* head){
    if(head == NULL) {
        return ;
    }
    cout << "val = "  << head->value << ' ';
    pre_traversal(head->left);
    pre_traversal(head->right);
}
void pre(Node* head) {
    stack<Node*> stk;
    if(head == NULL) {
        return ;
    }
    stk.push(head);

    while (!stk.empty())
    {
        Node* t = stk.top();
        cout << "val = "  << t->value << ' ';
        stk.pop();
        // 有右孩子压栈右边孩子，有左孩子就压栈左孩子
        if(t->right != NULL) {
            stk.push(t->right);
        }
        if(t->left != NULL) {
            stk.push(t->left);
        }       
    }
}
/*用head->right left就死循环 */ 
void in_traversal(Node* head){
    if(head == NULL) {
        return ;
    }
    in_traversal(head->left);
    cout << "val = "  << head->value << ' ';
    in_traversal(head->right);
}
void in(Node* head) {
    if(head == NULL) {
        return ;
    }

    stack<Node*> stk;
    // 左孩子不为空就遍历左边

    //【1】整条左边界依次入栈。
    // 【2】无法入栈时，弹出节点、来到弹出节点的右边界执 行条件1.
    // 复用head 绝了
    while(!stk.empty() || head != NULL) {
        // 把左边界入栈
        if(head != NULL) {
            stk.push(head);
            head = head->left;
        } else {
            head= stk.top();stk.pop();
            cout << "val = "  << head->value << ' ';
            head = head->right;
        }  
    }

}
void order_traversal(Node* head){
    if(head == NULL) {
        return ;
    }
    order_traversal(head->left);
    order_traversal(head->right);
    cout << "val = "  << head->value << ' ';
}
void order(Node* head) {
    if(head == NULL) {
        return NULL;
    }
    stack<Node*> stk1,stk2;
    stk1.push(head);
    while (!stk1.empty() || head != NULL) {
        stk2.push(stk1.poo());
    }




}
int main()
{
    Node a(1);
    Node b(2);
    Node c(3);
    Node d(4);
    Node e(5);
    Node f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    // pre_traversal(&a);
    // cout << "\n====" <<endl;
    // pre(&a);
    // cout << endl;

    in_traversal(&a);
    cout << "\n====" <<endl;
    in(&a);
    cout << endl;

    // order_traversal(&a);
    // cout << endl;



    return 0;
}