526互联

算法学习Day15二叉树、迭代与递归

发布时间 2023-12-28 09:55:56作者: HQWQF

Day15二叉树、迭代与递归

By HQWQF 2023/12/27

笔记

102.二叉树层序遍历

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

示例 1：

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

递归法

为了把不同层的节点放到不同的列表中，我们可以使用一个变量记录当前深入到的层的层数，将这个层数对应目标列表的下标，这样我们使用前序遍历的顺序遍历节点，但是通过发散式地输出节点到结果列表来实现层序遍历。

代码

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        //深度从0开始，如果当前深度等于外层列表元素数，说明初入该层
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

迭代法

我们可以使用一个队列来处理层序遍历的顺序，将根节点加入队列中，然后输出队列首节点并把节点的非空左右孩子加入队列，然后把自己弹出，此后持续为队列首节点作此处理，直到队列空。

顺序搞定了，但是如何把同一层的节点放到同一个列表中呢，观察整个处理过程中的队列的情况，我们可以发现在某些时刻，队列中存在的都是同一层的节点且全员到齐，此时我们可以新建该层的列表并在后续加入节点至其中。为了捕捉到这些时刻，我们可以想办法将这些时刻间的过程作为一次循环的过程，注意观察这些时刻之间的递进关系。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入： root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]

递归法

要将一棵二叉树翻转，只需要把所有的节点的左右孩子指针翻转即可，我们可以在遍历时顺便翻转。

递归法代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        Traversal(root);
        return root;
    }
    void Traversal(TreeNode* cur)
    {
        if(cur == nullptr)
        {
            return;
        }
        swap(cur->left,cur->right);
        Traversal(cur->left);
        Traversal(cur->right);        
    }
};

迭代法

同样，只要能遍历节点就行，迭代法也可以。

迭代法代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        vector<int> result;
        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;
    }

};

注释

  • 在翻转二叉树时若简单使用中序遍历，会导致部分节点被遍历两次并遗漏部分节点，这是因为中序遍历对左子树处理后翻转左右孩子，然后处理右子树，此时处理的右子树其实是翻转过来的左子树。

101.对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

迭代法

首先，我们可以通过用两种不同的顺序遍历二叉树后对比来确定其是否为对称，比如在统一迭代法的基础上分别为根节点的两个孩子建立队列，然后中添加后续节点入队列时，两个队列添加左右孩子的顺序相反，之后持续对比队列首。

注意这个情况我们需要把null也作为节点加入，不然我们没法区分没有兄弟的叶子节点是左还是右。

其实我们可以使用一个队列，每次将根节点的两个子树对称位置的节点的孩子成对（左子树的右配右子树的左，以此类推）加入队列，每次对比也是从队列中连续拿出两个（由于放入的规则，拿出的节点也是对称位置的）。这个情况我们也需要把null也作为节点加入，注意做好null的判断。

迭代法代码

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左右对称节点全空，此时说明是对称的
                continue;
            }

            // 左右对称节点不全空但有空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

递归法

使用递归的思想，只要根节点的左右子树各自的左右子树都是对称的即可，为了检查子树的对称我们又要检查子树的子树。

对于两个子树的对称位置上的两个节点，只要对比节点下的对称位置上的节点是否相等即可。

递归法代码

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   
        bool inside = compare(left->right, right->left);
        //子树根节点的左右子树的对称性相与，得到子树的对称性    
        bool isSame = outside && inside;                    
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};