理论基础

二叉树种类

满二叉树：每一层都填满，只有度为0或者2的节点，共有2^k - 1个节点（从1开始算层）。
完全二叉树：除最底层可能没被填满，其余每层都是满的（节点数量为2^（k - 1）），且最底层节点靠左。
二叉搜索树：有序树，左小右大。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉搜索树：AVL树，要么空，要么左右两个子树的高度差不超过1，且都是平衡二叉搜索树，AVL树是map,set,multimap,multiset的底层实现，插入和查询的时间复杂度是O(logn)。

二叉树存储方式

方便起见用链表，用数组也可以，i的左孩子是2 * i + 1,右孩子是2 * i + 2。

二叉树的遍历方式

广度优先遍历

层次遍历（迭代法）。

深度优先遍历

前序遍历（递归法、迭代法）
中序遍历（递归法、迭代法）
后序遍历（递归法、迭代法）

前序、中序、后序指的是中间节点的位置。

递归遍历

alt

控制放入数组那一行的位置即可。

前序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;

    }
    void traverse(TreeNode* cur, vector<int> &result) {
        if(cur == nullptr) return;
        result.push_back(cur->val); //中
        traverse(cur->left, result); //左
        traverse(cur->right, result); //右

    } 
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Traverse(root, result);
        return result;
    }
    public void Traverse(TreeNode cur, List<int> result) {
        if (cur == null) {
            return;
        }
         result.Add(cur.val);
        Traverse(cur.left, result);
        Traverse(cur.right, result);

    }
}

中序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;

    }
    void traverse(TreeNode* cur, vector<int> &result) {
        if(cur == nullptr) return;

        traverse(cur->left, result); //左
        result.push_back(cur->val); //中
        traverse(cur->right, result); //右

    } 
};


public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Traverse(root, result);
        return result;
    }
    public void Traverse(TreeNode cur, List<int> result) {
        if (cur == null) {
            return;
        }

        Traverse(cur.left, result);
        result.Add(cur.val);
        Traverse(cur.right, result);

    }
}

后序

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;

    }
    void traverse(TreeNode* cur, vector<int> &result) {
        if(cur == nullptr) return;
        traverse(cur->left, result);
        traverse(cur->right, result);
        result.push_back(cur->val);
    } 
};


public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Traverse(root, result);
        return result;
    }
    public void Traverse(TreeNode cur, List<int> result) {
        if (cur == null) {
            return;
        }
        Traverse(cur.left, result);
        Traverse(cur.right, result);
        result.Add(cur.val);
    }
}

迭代遍历

前序

前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，可以直接用栈进行遍历（省去了指针来进行遍历，栈本来只用来保存访问过的元素），所以才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

注意先入栈右节点才能保证出栈是中左右，用栈模拟递归，但实际上入栈顺序和递归入栈是不同的，模拟的栈左右子节点一起入栈（递归实际上是左一直入栈，回溯的时候右才入栈），模拟了递归的整个流程。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == nullptr) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* tmp = st.top();
            st.pop();
            result.push_back(tmp->val);//中
            if (tmp->right != nullptr)//左
            st.push(tmp->right);
            if (tmp->left != nullptr)//右
            st.push(tmp->left);
            
        }
        return result;
    }
};

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<TreeNode>();
        List<int> result = new List<int>();
        if (root == null) return result;
        st.Push(root); 
        while (st.Count != 0) {
            TreeNode tmp = st.Pop();
            result.Add(tmp.val);
            if(tmp.right != null) st.Push(tmp.right);
            if(tmp.left != null) st.Push(tmp.left);
        }
        return result;
    }
}

中序

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的，所以要先进行访问（遍历到底之前只移动指针不输出），保存访问到的元素，再逆序处理。

用一个指针遍历树（前序和后序直接使用的是栈进行遍历），栈用来记录遍历过的元素，也就是中，先按左做遍历，再一个个弹出栈里的中元素，再向右遍历。判断逻辑就是指针为空，栈弹出元素，指针不为空指针指向元素入栈。

指针为空栈里弹出一个新节点处理并继续处理它的右指针。

当指针为空时回退有两种情况，左指针为空是上一层的中，右指针为空是上n层的中（中已经处理过了）。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>result;
        stack<TreeNode*>st;
        TreeNode* cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;//左
            }else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);//中
                cur = cur->right;//右
            }
        }
        return result;
    }

};

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<TreeNode>();
        List<int> result = new List<int>();
        TreeNode cur = root;
        while (cur != null || st.Count != 0) {
            if(cur != null) {
                st.Push(cur);
                cur = cur.left;
            } else {
                cur = st.Peek();
                st.Pop();
                result.Add(cur.val);
                cur = cur.right;
            }
        }
        
        return result;
    }
}

后序

前序的左右颠倒一下，结果再反转一下，直接写很麻烦。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == nullptr) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* tmp = st.top();
            st.pop();
            result.push_back(tmp->val);
            if (tmp->left != nullptr)
            st.push(tmp->left);
            if (tmp->right != nullptr)
            st.push(tmp->right);

            
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<TreeNode>();
        List<int> result = new List<int>();
        if (root == null) return result;
        st.Push(root); 
        while (st.Count != 0) {
            TreeNode tmp = st.Pop();
            result.Add(tmp.val);
            if(tmp.left != null) st.Push(tmp.left);
            if(tmp.right != null) st.Push(tmp.right);

        }
        result.Reverse();
        return result;
    }
}

统一迭代

二刷再看。

二刷

二叉树递归遍历

太简单，不放了。

非递归迭代遍历

总结一些精华，随想录上前序的模拟递归入栈方式和实际递归不一样，模拟递归左右节点一起入栈，且是先入右后入左，而中序的模拟递归就和实际递也不一致，入栈遍历的顺序是中左（一直左）右，只不过处理的时候是先左（到底才开始处理），再中（处理时弹出一个元素），后右（遍历右，这个顺序是没变的），处理的思想和递归是一致的（左到底，再右），实际上栈只是起到记录元素的作用，不用被其约束。

很重要的一点，不考虑中，递归的入栈实际是一直入左到底，再一步步回溯入右！，先序的堆栈模拟是左右同时入栈

前序迭代

初始化维护一个栈，将根节点入栈。
当栈不为空时
弹出栈顶元素 node，将节点值加入结果数组中。
若 node 的右子树不为空，右子树入栈。
若 node 的左子树不为空，左子树入栈。


class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        st.push(root);
        if (root == nullptr) return res;
        while (!st.empty()) {
            TreeNode* temp = st.top();
            res.push_back(temp->val);
            st.pop();
            if (temp->right) st.push(temp->right);
            if (temp->left) st.push(temp->left);
        }
        return res;

    }
};

中序迭代

初始化一个空栈。
当【根节点不为空】或者【栈不为空】时，从根节点开始
若当前节点有左子树，一直遍历左子树，每次将当前节点压入栈中。
若当前节点无左子树，从栈中弹出该节点，尝试访问该节点的右子树，重复上一步。

当前指针为空，栈不为空，即指针遍历到叶子节点，这时候要往上回退从栈中取元素向上一层（左指针为空）或上n层（右指针为空）的右子树遍历。指针不为空，栈为空，此时对应回退到第一层根节点刚被从栈中弹出要往最大的右子树转的时候，需要继续处理根节点的右子树，直到指针再次遍历到叶子节点，栈也为空，遍历完成。


class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == nullptr) return res;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
               st.push(cur);
               cur = cur->left;
            }
            else {
                //回退
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

后序遍历

把前序入栈颠倒一下，再把结果reverse一下。

    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == nullptr) return res;
        st.push(root);
        while (!st.empty()) {
            TreeNode* temp = st.top();
            st.pop();
            res.push_back(temp->val);
            if (temp->left) st.push(temp->left);
            if (temp->right) st.push(temp->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }

和递归一致的写法，

初始化一个空栈。当【根节点不为空】或者【栈不为空】时，从根节点开始

每次将当前节点压入栈中，如果当前节点右左子树，就往左子树跑，没有左子树就往右子树跑。
若当前节点无左子树也无右子树，从栈中弹出该节点，如果当前节点是上一个节点（即弹出该节点后的栈顶元素）的左节点，尝试访问上个节点的右子树，如果不是，那当前栈的栈顶元素继续弹出。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == nullptr) return res;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            while (cur != nullptr) {
                st.push(cur);
                if (cur->left) cur = cur->left;//左
                else cur = cur->right;//右
            }
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            //回溯
            if (!st.empty() && st.top()->left == cur) {
                //当前节点是左子节点，那继续遍历右子节点
                cur = st.top()->right;
            }
            else {
                //此时当前子树都已经走完了，节点置为null，不要再往下重复递归遍历了
                cur = nullptr;
            }
        }
        return res;
    }
};

统一写法

其实按照中序的模拟递归思路是一致的，先指针向左走到底，再一步步回退走右，因为不管有没有中，左右的递归调用顺序是不变的（用栈记录访问过的元素也是不变的），按照中序的写法改一下顺序即可得到前序,前序改一下左右，结果翻转一下就能得到后序。

总结不同的遍历顺序的递归调用过程都是一样的，本质实际就是在递归的不同时机输出，那对于根节点来说，它要被搞 3 次：

第 1 次经过它，去向左子树，此时输出就是先序。
第 2 次从左子树回来，经过它，去向右子树，此时输出就是中序。
第 3 次从右子树回退到它，此时输出就是后续。

alt

//前序
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == nullptr) return res;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                res.push_back(cur->val);//中
               st.push(cur);
               cur = cur->left; //左
            }
            else {
                //回退
                cur = st.top();
                st.pop();
                cur = cur->right; //右
            }
        }
        return res;
    }
};
//后序 前序倒一下
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == nullptr) return res;
        TreeNode* cur = root;
        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                res.push_back(cur->val);//中
               st.push(cur);
               cur = cur->right; //左
            }
            else {
                //回退
                cur = st.top();
                st.pop();
                cur = cur->left; //右
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }

三刷再看看后序的非迭代方式

[代码随想录一刷&二刷] day14 二叉树