关于算法:算法数据结构-二叉树的几种操作方法及思考

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

• 递归遍历
  首先，回顾一下其余的数据结构，如数组，链表，栈和队列，比拟少的呈现递归的操作，一遍都是间接遍历循环。之所以在二叉树的体系里呈现递归，和树的数据结构的特点相干：由 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;
    }
};

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