[算法数据结构] 二叉树的几种操作方法及思考

二刷代码随想录，在做二叉树的时候总结一下规律，以加深对二叉树的理解。

• 递归遍历
  首先，回顾一下其他的数据结构，如数组，链表，栈和队列，比较少的出现递归的操作，一遍都是直接遍历循环。之所以在二叉树的体系里出现递归，和树的数据结构的特点相关：由root节点和左右节点及节点的节点...构成。本质上是存在一个指针的不断链接。因此和数组这种地址连续的结构相比，树的节点没有办法通过依次寻找地址来遍历。所以，递归派上了用场。倘若树是一个单叉树，问题倒没有那么复杂（不存在前序，后序，中序遍历），只要不断将子节点传给递归函数，操作在遍历之前或者之后。递归函数的意义可以理解为他通向最后不能在递归的地方为止。因此递归函数在代码的位置非常重要，控制着代码的逻辑。

• 递归遍历的举例
  以前序遍历为例，前序遍历是指中左右的遍历方式，“前”是指中间节点首先遍历。

  class Solution {
  public:
    void traversal(TreeNode* cur, vector<int>& result) {
        if (cur == NULL) return ;
        result.push_back(cur->val);
        traversal(cur->left, result);
        traversal(cur->right, result);
    }
  
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traversal(root, ans);
        return ans;
    }
  };

  1.首先是构造递归函数，首先他是个函数，得考虑传入参数，返回值。传入参数基本上肯定需要树的节点传入，这样在函数里面才能通过调用递归函数，并将当前的节点的左右节点传入，实现递归的功能。
  2.顺序。因为是前序遍历，所以我们需要保证先对树的中间节点进行操作，那么由于传入的root就是一个中间节点，所以需要对其先进行操作。然后再traversal(left) , traversal(right)。

• 层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            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;
    }
};

如何理解层序遍历和普通遍历之间的异同？在我看来，层序遍历蕴含的是前序遍历的思想。首先在思考如何实现层序遍历时，我们需要思考的问题的是如何避免树在当前节点一直递归下去。因为如果那样的话就无法实现一层一层的输出了。所以我们需要构造一个容器去维护每一层的节点，这里选择队列que。在遍历当前节点的时候把他的左右节点依次放入队列。然后再去实现遍历一层的功能，十分的巧妙。

• 一个实例：翻转二叉树

class Solution {
public:
    void traversal(TreeNode* cur) {
        if (cur == NULL) return ;
        TreeNode* node = cur->left;
        cur->left = cur->right;
        cur->right = node; 
        traversal(cur->left);
        traversal(cur->right);
    }

    TreeNode* invertTree(TreeNode* root) {
        traversal(root);
        return root;
    }
};

可以用层序遍历也可以用前序遍历或者后续遍历。这一次总结的时候在思考应该用什么遍历顺序，想到了其实后序遍历也是可以的，即可以把调用递归函数的两行放在调换的前面。