二叉树 算法

二叉树
基本概念：

树的算法求解本质上：是递归运算

树的遍历：前序：根左右；中序：左根右；后序：左右根

完全二叉树： 叶子节点所在的层，总是靠左连续的。

满二叉树： 每个节点度为2，除了叶子节点。

二叉查找树/二叉搜索树：左小于根，右大于根。

 平衡二叉树：左右子树的深度差不超过1

二叉树算法题模板

1： 使用递归完成树的前中后序遍历
main(TreeNode* root) { // 根节点

        // 1: 结果集，存放每个节点的元素
        // vector<int> res;

        // 2: 判断root
        // if (root == nullptr) return res;

        // 3：递归进行遍历
        // df(root, res)
       
}

void df(TreeNode* root, vector<int> &res)
{
    // 结束递归
    if (root == nullptr)
        return;
    
    // 递归遍历
   
    // res.push_back(root->val); // 前序遍历，根左右， 先存放根节点数据
     
    // 左子树 递归
    if (root->left)
        df(root->left, res);
    
    // res.push_back(root->val); // 中序遍历，左右根，中间存放

    // 右子树 递归
    if (root->right)
        df(root->right, res);
    
    // res.push_back(root->val); // 后序遍历， 左右根
}



2： 使用非递归-栈完成树的前中序遍历
main(TreeNode* root) { // 根节点

        // 1: 结果集，存放每个节点的元素
        // vector<int> res;

        // 2: 判断root
        // if (root == nullptr) return res;

        // 3: 栈stack
        stack<TreeNode*> s;

        // 4:  cur_node 指向树每次遍历的节点,不断变化搜索
        TreeNode* cur_tree_node = nullptr;
        cur_node = root; // 初始值指向root

        // 5： while 判断cur_node和s
        // if判断cur_node, 为空说明树的一侧搜索完毕，开始弹出父节点，搜索树的另一侧。

        // 
        while(cur_node != nullptr || !s.empty()) {
            if (cur_node != nullptr) {
                s.push(cur_node); // 当前节点进栈  
                
                //前序遍历
                // res.push_back(cur_node->val)
                
                // cur_node 左
                cur_node = cur_node->left;
            } else {
                cur_node = s.top();
                s.pop(); // 出栈父节点

                // 中序遍历
                // res.push_back(cur_node->val)
                
                // cur_node 右
                cur_node = cur_node->right
            }
        }

        // 6 
        return res;
}


3： 基于queue的层次遍历， 层次遍历也可以实现从上到下打印元素
main(TreeNode* root)
{
    // 1: 结果集，存放每个节点的元素
    // vector<int> res;

    // 2: 判断root
    // if (root == nullptr) return res;

    // 3: 队列q存放当前层的节点
    queue<TreeNode*> q;
    q.push(r