(第26天)【leetcode题解】226、翻转二叉树 589、N叉树的前序遍历 590、N叉树的后序遍历

226、翻转二叉树

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

思路

• 题目分析：只需要把每个节点的左右孩子交换一下就可以实现整体翻转的效果。
• 解法：在遍历过程中，把每个遍历到的节点的左右孩子进行交换。

代码

1.层序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                TreeNode* tempNode = node -> left;
                node -> left = node -> right;
                node -> right = tempNode;
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return root;
    }
};

2.前序遍历(递归法)：

1. 递归函数的参数和返回值：当前节点的指针、返回root节点的指针
2. 终止条件：参数代表的当前节点为空时终止
3. 递归逻辑：前序遍历顺序为中左右，因此先翻转节点、向左递归、向右递归。

class Solution {
public:
    //参数：root代表当前节点
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;//终止条件
        swap(root -> left, root -> right);//中
        invertTree(root -> left);//左
        invertTree(root -> right);//右    
        return root;//返回值
    }
};

3.前序遍历(迭代法)：

class Solution {
public:
    //参数：root代表当前节点
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node -> right) st.push(node -> right);//右
                if (node -> left) st.push(node -> left);//左
                st.push(node);//中
                st.push(NULL);//标记
            } else {
                st.pop();//先取出标记
                node = st.top();//中
                st.pop();
                swap(node -> left, node -> right);//翻转
            }
        }
        return root;
    }
};

589、N叉树的前序遍历

题目描述

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

思路

1.递归法：

1. 返回值：无；参数：cur指向当前节点的指针、
2. 终止条件：cur为NULL时
3. 递归逻辑：前序遍历中左右

2.迭代法：

• 每次遍历到一个节点，先把这个节点的值加入结果集。
• 为了确保下一个遍历到的节点每次都是当前节点从左到右第一个子节点，把当前节点的所有子节点从右到左压入栈中。
• 这样每次从栈顶取出元素都能确保是按照前序遍历的顺序。

代码

1.递归法：

class Solution {
public:
    //递归函数
    //参数：cur指向当前节点; res结果集
    void helper(Node* cur,vector<int>& res) {
        if (cur == NULL) return;//终止条件
        res.push_back(cur -> val);//中
        //递归逻辑：先顺着每个节点的靠左的子节点递归
        for (Node* & ch : cur -> children) {
            helper(ch, res);
        }
    }

    vector<int> preorder(Node* root) {
        vector<int> res;//结果集
        helper(root, res);
        return res;
    }
};

2.迭代法：

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if (root == NULL) return res;
        stack<Node*> st;
        st.push(root);
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            res.push_back(node -> val);
            for (int i = node -> children.size() - 1; i >= 0; i--) {
                st.push(node -> children[i]);//把当前节点的所有子节点从右到左放入栈中
            }
        }
        return res;
    }
};

590、N叉树的后序遍历

题目描述

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

思路

1.递归法：

1. 返回值：无；参数：cur当前节点、res结果集
2. 终止条件：当前节点cur为NULL时
3. 递归逻辑：左右中，先通过递归，到最底层的最左边的节点，然后开始把节点值加入结果集。

2.迭代法：

1. 按照上面前序遍历的模板，把子节点压入栈的顺序颠倒一下(从右到左压入栈变成从左到右压入栈)，那么最终结果集中的顺序为中右左。
2. 在把结果集翻转一下，顺序就变成了左右中，为后序遍历的顺序。

代码

1. 递归法：

class Solution {
public:
    //递归函数
    //参数：cur当前节点、res结果集
    void helper(Node* cur, vector<int>& res) {
        if (cur == NULL) return;//终止条件
        for (Node* ch : cur -> children) {
            helper(ch, res);
        }
        res.push_back(cur -> val);//中
    }

    vector<int> postorder(Node* root) {
        vector<int> res;
        helper(root,res);
        return  res;
    }
};

2.迭代法：

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        stack<Node*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            res.push_back(node -> val);//中
            for (Node* ch : node -> children) {
                st.push(ch);//把当前节点的所有子节点从左到右压入栈中
            }
        }
        reverse(res.begin(), res.end());//将结果集翻转
        return res;
    }
};

思考总结

1. 树的操作都要在遍历的基础上，在遍历的过程中添加某些操作。
2. 二叉树节点定义：

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

创建二叉树节点时要用new TreeNode(num)
3. 递归三要素：确定参数和返回值、确定终止条件、确定递归逻辑
4. 树的迭代遍历：深度优先遍历离不开栈、广度优先遍历离不开队列