C++ 二叉树

一 树的概念

二 二叉树

满二叉树：

定义：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

最后一层的节点个数等于其他层数节点个数之和+1，假设第k层，最后一层的节点个数即2*（k-1）

完全二叉树：

定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的遍历

非递归写法

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> his;
        vector<int> res;
        TreeNode *t = root, *dummy = new TreeNode(0);
        his.push(dummy);
        while(!his.empty()){
            while(t){
                res.push_back(t->val);
                his.push(t);
                t = t->left;
            }
            t = his.top()->right;
            his.pop();  
        }
        return res;
    }
};

容易理解的写法

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

中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            top = stack.pop() #此时左子树遍历完成
            res.append(top.val)  #将父节点加入列表
            cur = top.right #遍历右子树
        return res

后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right  #先将右节点压栈
            top = stack.pop()  #此时该节点的右子树已经全部遍历完
            cur = top.left  #对左子树遍历
        return res[::-1]  #结果翻转

统一形式

先序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;  //保存结果
        stack<TreeNode*> st;  //调用栈
        if(root!=nullptr) st.push(root);  //首先介入root节点
        while(!st.empty()){
            TreeNode *t = st.top();
            st.pop();  //访问过的节点弹出
            if(t!=nullptr){
                if(t->right) st.push(t->right);  //右节点先压栈，最后处理
                if(t->left) st.push(t->left);
                st.push(t);  //当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
                st.push(nullptr);  //在当前节点之前加入一个空节点表示已经访问过了
            }else{  //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
                res.push_back(st.top()->val);  //st.top()是nullptr之前压栈的一个节点，也就是上面st.push(t)中的那个t
                st.pop();  //处理完了，第二次弹出节点（彻底从栈中移除）
            }
        }
        return res;
    }
};

打赏