Skip to content

Latest commit

 

History

History
285 lines (216 loc) · 7.45 KB

二叉树.md

File metadata and controls

285 lines (216 loc) · 7.45 KB

假设树节点的定义如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

(前中后序)遍历

  • 前序遍历：根->左->右
  • 中序遍历：左->根->右
  • 后序遍历：左->右->根

递归版

//前序遍历
void preorderTraversalRecursion(TreeNode *node)
{
    if(!node) return;
    cout << node->val << " ";//操作当前节点
    preorderTraversalRecursion(node->left);
    preorderTraversalRecursion(node->right);
}

//中序遍历
void inorderTraversalRecursion(TreeNode *node)
{
    if(!node) return;
    inorderTraversalRecursion(node->left);
    cout << node->val << " ";//操作当前节点
    inorderTraversalRecursion(node->right);
}

//后序遍历
void postorderTraversalRecursion(TreeNode *node)
{
    if(!node) return;
    postorderTraversalRecursion(node->left);
    postorderTraversalRecursion(node->right);
    cout << node->val << " ";//操作当前节点
}

迭代版

需要使用一个栈作为辅助空间

//前序遍历
void preorderTraversalIteration(TreeNode *root)
{
    stack<TreeNode*> st;
    if(root)
        st.push(root);

    while(!st.empty()){
        TreeNode *nd = st.top();
        st.pop();

        cout << nd->val << " ";//操作当前节点

        if(nd->right)
            st.push(nd->right);
        if(nd->left)
            st.push(nd->left);
    }
}

//中序遍历：
void inorderTraversalIteration(TreeNode *root)
{
    stack<TreeNode*> st;

    TreeNode *curr = root;

    while(curr || !st.empty()){
        if(curr){
            st.push(curr);
            curr = curr->left;
        }
        else{
            curr = st.top();
            st.pop();

            cout << curr->val << " ";//操作当前节点

            curr = curr->right;
        }
    }
}

//后序遍历
void postorderTraversalIteration(TreeNode *root)
{
    stack<TreeNode*> st;
    TreeNode *pre;

    if(root)
        st.push(root);

    while(!st.empty()){
        TreeNode *nd = st.top();
        /*
         * 出栈条件：
         * 对于叶子节点：直接弹出
         * 对于非叶子节点：如果已经遍历过其左子节点或右子节点，则弹出
         */
        if((!nd->left && !nd->right) || (pre && (nd->left == pre || nd->right == pre))){
            st.pop();
            cout << nd->val <<" ";//操作当前节点
            pre = nd;
        }
        else{//说明是一个非叶子节点，并且还未访问其左右孩子
            if(nd->right)
                st.push(nd->right);
            if(nd->left)
                st.push(nd->left);
        }
    }
}

对于后序遍历，由于其访问序列为：左->右->根。因此还有一种方法，可以按类似前序遍历的方式：根->右->左，然后对得到的结果反序

相关题目：

  • 剑指offer(8):二叉树的下一个节点
  • 剑指offer(28):对称的二叉树

二叉树重建

根据前序、中序序列重建二叉树

前序序列的特点：{首元素，左子树节点，右子树节点} 中序序列的特点：{左子树节点，首元素，右子树节点}

因此，可以根据前序序列的首元素创建根节点，然后遍历中序序列，找到首元素，递归处理左子树和右子树。函数返回（树或子树的）根节点，每个新创建节点分别将左右子节点设置为递归处理的返回节点

如何处理前序序列和中序序列不匹配等非法输入的情况？（throw std::exception("Invalid input")）

相关题目：剑指offer(7):重建二叉树

根据前序、后序序列重建二叉树（不可行）

后序序列中，根节点在末尾，前序序列中，根节点在首部，无法确定左右子树节点的范围，因此无法重建

根据中序、后序序列重建二叉树

和根据前序、中序序列重建的思想一样

二叉树序列化

序列中存储空节点信息（如使用‘$’）可以使用前序序列重建二叉树

相关题目：

  • 剑指offer(37):序列化二叉树

(广度优先)遍历

使用队列

void depthTraversal(TreeNode *root)
{
    deque<TreeNode*> d;
    if(root)
        d.push_back(root);

    TreeNode *curr;
    while(!d.empty()){
        curr = d.front();
        d.pop_front();

        cout << curr << " ";

        if(curr->left)
            d.push_back(curr->left);
        if(curr->right)
            d.push_back(curr->right);
    }
}

相关题目：

  • 剑指offer(32):不分行从上到下打印二叉树(题目一)
  • 剑指offer(32):分行从上到下打印二叉树(题目二)
  • 剑指offer(32):之字形打印二叉树(题目三)

路径

使用辅助空间保存路径（如vector）

/*
 * 函数获取到达节点dest的路径
 * dest是否为nullptr的检查应该在外层，因为该函数是一个递归的过程，一旦dest不为空，后续的递归都不会为空
 * 如果查找的节点不存在树中，可以通过path中的元素或者函数返回值判断
 */
bool getPathCore(TreeNode *root,TreeNode *dest,vector<TreeNode*> &path)
{
    if(!root)
        return false;

    //首先假设当前节点是所要查找路径中的一个节点，插入
    path.push_back(root);

    if(root == dest) //先判断当前节点是否是查找的节点(前序遍历)
        return true;

    bool find = false;

    //如果左子树中找到，则不会继续对右子树进行查找
    find = getPathCore(root->left,dest,path) || getPathCore(root->right,dest,path);

    //左子树或右子树中找到则直接返回（因为路径中肯定包含了当前节点，不返回会弹出）
    if(find)
        return find;

    //如果(左右)子树中都没找到，说明所要查找的路径不经过这个节点，弹出
    path.pop_back();

    return false;
}

相关题目：

  • 剑指offer(34):二叉树中和为某一值的(所有)路径

深度

int TreeDepth(TreeNode* pRoot)
{
    if(!pRoot)
        return 0;
    
    int depth1 = 1 + TreeDepth(pRoot->left);
    int depth2 = 1 + TreeDepth(pRoot->right);
    
    return depth1 > depth2 ? depth1 : depth2;
}

相关题目：

  • 剑指offer(55):二叉树的深度(题目一)
  • 剑指offer(55):平衡二叉树AVL(题目二)

理论知识

两种特殊二叉树

  • 满二叉树：除叶子节点外的所有分支节点都含有2个非空子节点的二叉树
  • 完全二叉树：除了最后一层，其余层都是“满”的，这样的二叉树是完全二叉树

二叉树定理

  1. 满二叉树定理：非空满二叉树的叶节点数等于其分支节点数加1
  2. 一颗非空二叉树空子树的数目等于其节点数目加1
  3. 任意二叉树度数为2节点的个数等于叶节点个数减1