day14 二叉树(一)

2023-12-13 11:03:17

day14
代码随想录
2023.12.12
关于树得操作也是比较熟悉得,手推各种操作的结果,各种树得性质等等,但对于代码实现还是有些生疏,借此机会巩固一下

1. 144二叉树的前序遍历
二叉树的深度遍历三种情况,前序中序后序,逻辑都一样,顺序不同罢了,递归是最简单的实现方法,也没什么可具体解释的,直到节点为空时递归结束。至于另外两种,只是顺序不同罢了,就不细说了。

/**
 * 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 travel(TreeNode*node, vector<int>& result){
        if(node==NULL){
            return;
        }
        result.push_back(node->val);
        travel(node->left, result);
        travel(node->right, result);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        travel(root, result);
        return result;
    }
};

下面介绍迭代的方法:递归本质就是一个栈实现的,而迭代就是将这个栈手动实现。大致思想就是将根节点压入栈中,然后循环遍历,先弹出栈口节点,获得value,然后看该节点有没有子节点,按照先右后左的顺序再将两个子节点压入栈中,这里有一点要注意,为什么先右后左,前序遍历不应该是中左右吗?因为栈是先进的后访问,后进的先访问,因此先右后左,这样先访问的是左节点。循环的条件是栈不为空,若为空,则表示遍历完了,return就行,但要注意,每次入栈要保证节点不为空,开始写代码就是忘了该条件,导致一直循环,退不出去,执行超时了。

/**
 * 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*> st;
        if(root==NULL)
            return result;
        st.push(root);
        while(!st.empty()){
            TreeNode*node = st.top();
            result.push_back(node->val);
            st.pop();
            if(node->right) st.push(node->right);
            if(node->left) st.push(node->left);
        }
        return result;
    }
};

当然,迭代法写遍历有缺点,上述代码只适用于前序和后序遍历,后序遍历只需要将子节点入栈顺序更改即可。但中序遍历写法就完全不同了。是另一种风格:
这里是代码不同的原因:因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。
因此代码实现逻辑则是,用指针控制遍历节点顺序,一直往左下遍历,直到指针为空,然后依次返回,返回途中处理result值,

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点,访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据,就是要处理的数据(放进result数组里的数据)
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

当然,迭代法还是有办法实现三种遍历统一代码的,详情见代码随想录:统一遍历

文章来源:https://blog.csdn.net/qq_56913257/article/details/134942233
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。