二叉树

树是有限个(n>0)元素组成的集合。

树中每个结点拥有的孩子结点的个数称为该结点的度，度为0的结点为叶子结点或终端结点。树的度是树中结点的度的最大值。在有序树中，孩子结点沿用左边大、右边小的原则。

二叉树是有限个(n>=0)结点的集合。可以为空，或者有一个结点作为根结点，其他结点分成左右两个互不相交的子集作为二叉树的左右子集。

从形式上看二叉树似乎是每个结点最多有两个孩子的树，但实际上，二叉树和树是两种完全不同的结构。树是实际存在的结构类型，而二叉树不是一棵特殊的树，更多的作为一种工具。二叉树中结点数可以为0，而树不可以为0；二叉树的左右孩子要明确的指出是右还是左。

遍历：之所以叫前序、中序、后序遍历，是因为根节点在前、中、后。

对于上面的二叉树，我们遍历有：

前序：F,B,A,D,C,E,G,I,H

中序：A,B,C,D,E,F,G,H,I

后序：A,C,E,D,B,H,I,G,F

删除节点时，删除过程按照后序遍历的顺序。删除一个节点时，先删除它的左节点和右节点，再删除节点本身。

后序遍历在数学表达式中应用广泛。

通过中序遍历，我们可以得到原式：4*(7-2)+5。但程序表达在处理时中序遍历并不容易，因为要区分优先级。我们可以通过后序遍历，使用栈来处理表达式。每遇到一个操作符，就从栈顶弹出两个元素，计算并将结果返回到栈中。

A.前序遍历

方法一：递归。

定义preorder(root)表示当前遍历到root节点的答案，首先将root节点的值输入答案，再调用preorder(root->left)来遍历左子树，preorder(root->right)来遍历右子树。

class Solution{
public:
    void preorder(TreeNode *root,vector<int> &res){
        if(root==nullptr) return;
        res.push_back(root->val);
        preorder(root->left,res);
        preorder(root->right,res);
    }
    vector<int> preorderTraversal(TreeNode *root){
        vector<int> res;
        preorder(root,res);
        return res;
    }
};

方法二：迭代

与递归不同的是，需要显示地将栈模拟出来，即给出入栈和出栈的部分。

class Solution{
public:
    //注意这里TreeNode后面*的位置，是与递归方法不一样的
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr){
            return res;
        }
        stack<TreeNode*> stk;
        TreeNode* node =root;
        while(!stk.empty()||node!=nullptr){
            while(node!=nullptr){
                res.emplace_back(node->val);
                stk.emplace(node);
                node=node->left；
            }
            node=stk.top();
            stk.pop();
            node=node->right;
        }
        return res;
    }
};