算法学习——LeetCode力扣二叉树篇1

算法学习——LeetCode力扣二叉树篇1

144. 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶

递归算法很简单，你可以通过迭代算法完成吗？

代码解析

递归遍历

前后中遍历的前后中，指的是中间节点。

前序遍历 ：中左右
后续遍历： 左右中
中序遍历： 左中右

/**
 * 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:
    void Traversal(TreeNode* cur , vector<int> &result)
    {
        if (cur == nullptr) return;
        result.push_back(cur->val);
        Traversal(cur->left , result);
        Traversal(cur->right , result);

    }

    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> result;
        Traversal(root,result);
        return 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> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> my_stack; 

        if(root == nullptr) return result;

        my_stack.push(root);//前序遍历是中左右，先处理一个中就是root

        while(my_stack.empty() != 1)
        {
            TreeNode* my_node = my_stack.top();//提前中节点
            my_stack.pop();
            //中节点压入结果
            result.push_back(my_node->val);
			//之后将中节点的左右子节点放到栈里，作为未来的中节点
			//压入栈的顺序和弹出栈是相反的，先遍历左再是右，所有先压入右再压入左
            if(my_node->right != nullptr) my_stack.push(my_node->right);
            if(my_node->left  != nullptr) my_stack.push(my_node->left);
        }

        return result;
    }
};

145. 二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

描述

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶

递归算法很简单，你可以通过迭代算法完成吗？

代码解析

递归遍历

/**
 * 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:
    void traversal(TreeNode* cur , vector<int> &result)
    {
        if (cur == nullptr) return;
        traversal(cur->left , result);
        traversal(cur->right , result);
        result.push_back(cur->val);

    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return 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> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> my_stack;

        if(root == nullptr) return result;

        my_stack.push(root);

        while(my_stack.empty() != 1)
        {
            TreeNode* my_node = my_stack.top();
            my_stack.pop();
            //和前序一样，但是变成中右左
            result.push_back(my_node->val);
            if(my_node->left != nullptr) my_stack.push(my_node->left);
            if(my_node->right != nullptr) my_stack.push(my_node->right);  
        }
		//反转，变成左右中
        reverse (result.begin() , result.end());
        return result;

    }
};

94. 二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶

递归算法很简单，你可以通过迭代算法完成吗？

代码解析

递归遍历

/**
 * 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:
    void traversal(TreeNode* cur , vector<int> &result)
    {
        if(cur==nullptr) return;
        traversal( cur->left , result);
        result.push_back( cur->val);
        traversal( cur->right , result);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return 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;
        stack<TreeNode*> my_stack;

        if(root == nullptr) return result;
        TreeNode* cur = root;

        while(cur != nullptr || my_stack.empty() != 1)
        {
            if(cur != nullptr)//找到cur的最左叶子节点
            {
                my_stack.push(cur);//找的过程中所有的左节点都存起来
                cur = cur->left;

            }else//处理中节点和右节点
            {
                cur = my_stack.top();//输出栈里之前存的左节点 ，这时左节点看作成中间节点
                my_stack.pop();

                result.push_back(cur->val);
                cur = cur->right;//然后找刚才输出左节点作为中间点时的右节点
            }

        }       
        return result;

    }
};

102. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

提示

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

代码解析

/**
 * 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<vector<int>> levelOrder(TreeNode* root) {

        vector<vector<int>> result;
        TreeNode* node ; //迭代节点
        queue<TreeNode*> my_que; //队列

        if(root == nullptr) return result;
        else // 根节点进队列
        {
            my_que.push(root);
        }

        while(my_que.empty() != 1)
        {
            int size = my_que.size(); //size是不断变化的，指每一层级的点数量
            vector<int> nums;//每一层级存放的点  
            //将每一层的点从队列弹出放入nums，并且下一个层级点放入队列
            for(int i=0 ; i<size ; i++) 
            {
                node = my_que.front(); //该层级的点弹出放入数组
                my_que.pop();
                nums.push_back(node->val);
                //每一个弹出点的下一个层级左右节点压入队列
                if(node->left != nullptr)    my_que.push(node->left);
                if(node->right != nullptr)   my_que.push(node->right);

            }
            result.push_back(nums);
        }
        return result;
    }
};