day14 二叉树（一）

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;
    }
};

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