代码随想录|day 13

Day 13 又出去玩了

附上一个学习链接：https://www.geeksforgeeks.org

具体页面：Introduction to Binary Tree - Data Structure and Algorithm Tutorials - GeeksforGeeks

一、理论学习

今天是回顾了二叉树中最重要的操作 : 遍历二叉树。我们可以将许多后续的问题转化成遍历二叉树来解决。那么遍历二叉树有两种，一种是递归去解决，另一种是非递归的算法。对于递归而言，我们要确定递归函数的参数和返回值要确定终止条件。要确定单层递归的逻辑，缺一不可。让我们以其中先序遍历为例，我们的终止条件是什么？终止条件是当前指针为空指针的时候就停止遍历。那我们传入的参数最重要的是什么？最重要的就是。要访问的节点。至于传入一个数组是为了方便我们去返回和记录，所以说最重要的还是我们的节点。当我们传入了节点之后，我们就确定了传入的参数，那也确定了我们的终止条件，也就是节点为空。那么我们的单层循环逻辑是什么呢？将根节点的值加入到数组，也就是处理我们的根节点，然后去遍历继续去处理我们根节点的左节点以及依次是他们的右节点。那么这样我们就讲完了前序遍历的递归算法，那么对应于后序还有中序都是类似的思路。

那么难点在哪里呢？难点在于非递归。而非递归之所以会产生前序后序是一组，而中序单独是一组的原因在于。前序遍历和后序遍历都可以通过某种方法使得我们遍历的。节点就是我们处理的节点，而中序遍历。遍历到的节点并不是我们当前就要处理的节点所以说会分成这两类。那么我们先说前序遍历前序遍历是最直观的。那我们想象想象一个土哦，我们在做非递归的时候要。善于去模拟。他整个执行的过程那我们先想象一个债，然后呢，我们将根节点入栈。然后我们是不是就应该处理我们的根节点了？我们把根节点弹出来，然后呢？接着去访问他的右节点，为什么是右节点呢？因为我们输出的顺序应该是，呃，跟左右，然而我们的栈是先进后出，所以说很明显我们应该先让他的右节点进栈。再让我们的左节点入栈。在此之前，我们让根节点出战了然后就让它打印输出就好了。不断地去循环就好。循环终止的条件是栈为空，对吧？好，那么后续是如何用前序来。改装的呢？我们看到前序的顺序应该是钟左右，那我们把。他改成中有左是不是也是可以的。中右左的顺序进行一个反转。是不是左右中啊？那这样的话，我们就通过这样一个手段完成了后续遍历。最后最重要的就是我们的中序遍历了对于中序遍历来说呢？我们需要一个指针来指向我们当前要去处理的这个元素。这次我们循环的条件是，呃，指针不为空或者。我们的战不为空。一开始我们要我们让。我们的指针，一路向左。将遍历到的元素都加入战中。直到我们处理到一个空节点。就让该元素出栈。出站之后，我们打印输出然后再去访问他的右节点。，我们去访问他的右节点。通过这样不停地循环，我们就能得到我们想要的遍历顺序。

part 1 二叉树基础概念回顾【刚考完还记得】附上备忘链接

代码随想录 (programmercarl.com)

Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

Binary Tree Data Structure

// Use any below method to implement Nodes of tree

// Method 1: Using "struct" to make
// user-define data type
struct node {
	int data;
	struct node* left;
	struct node* right;
};

// Method 2: Using "class" to make
// user-define data type
class Node {
public:
	int data;
	Node* left;
	Node* right;
};

二、刷题部分

递归遍历：

144.二叉树的前序遍历(opens new window)

/**
 * 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 preorde(TreeNode* root,vector<int>&ans){
         if(root==nullptr){
            return;
        }
        ans.push_back(root->val);
        preorde(root->left,ans);
        preorde(root->right,ans);

    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>ans;
        preorde(root,ans);
        return ans;
    }
};

145.二叉树的后序遍历(opens new window)

微微修改一下

/**
 * 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 preorde(TreeNode* root,vector<int>&ans){
         if(root==nullptr){
            return;
        }
        preorde(root->left,ans);
        preorde(root->right,ans);
        ans.push_back(root->val);

    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>ans;
        preorde(root,ans);
        return ans;

    }
};

94.二叉树的中序遍历

其实这三道题目是差不多的,递归部分做如下修改。

preorde(root->left,ans);
ans.push_back(root->val);
preorde(root->right,ans);

非递归：

144.二叉树的前序遍历(opens new window)

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


       }
        return ans;
    }
};

145.二叉树的后序遍历(opens new window)

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


       }
       reverse(ans.begin(),ans.end());
        return  ans;

    }
};

94.二叉树的中序遍历

/**
 * 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) {
        stack<TreeNode*>st;
        vector<int>ans;
        TreeNode* ptr=root;
        while(!st.empty()||ptr!=nullptr){
            if(ptr!=nullptr){
                st.push(ptr);
                //一路向左
                ptr=ptr->left;
            }
            else{
                ptr=st.top();
                st.pop();
                ans.push_back(ptr->val);
                ptr=ptr->right;
            }

        }
       return ans;
    }
};