二叉树专题

阳光穿透心脏的1/2处 2022-12-28 08:18 83阅读 0赞

## 二叉树的定义 ##

struct TreeNode { 
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) { }
    };

*  满二叉树：只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，深度为k，有2^k-1个节点。
 *  完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *  二叉搜索树：是一棵有序树。
    
     *  若其左子树不空，则左子树上所有节点的值均小于它的根节点的值
     *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
     *  它的左右子树也分别是二叉排序树
 *  平衡二叉搜索树
    
     *  它是一棵空树或它的左右两个子树的高度差绝对值不超过1
     *  且左右两个子树都是一棵平衡二叉树
 *  C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn；而unordered\_map、unordered\_set底层实现是哈希表。

## 二叉树的存储方式 ##

*  链式存储：指针，散落的结点
 *  顺序存储：数组，内存连续分布
    
     *  如果父节点的数组下表是i，那么它的左孩子就是i \* 2 + 1，右孩子就是 i \* 2 + 2。

## 二叉树的遍历方式 ##

*  深度优先遍历【栈】
    
     *  前序遍历（递归法，迭代法）
     *  中序遍历（递归法，迭代法）
     *  后序遍历（递归法，迭代法）
 *  广度优先遍历【队列】
    
     *  层次遍历（迭代法）

## 递归遍历二叉树的步骤 ##

**前序遍历**

1.  确定递归函数的参数和返回值

void traversal(TreeNode* cur, vector<int>& vec)

1.  确定终止条件

if (cur == NULL) return;

1.  确定单层递归的逻辑

vec.push_back(cur->val);    // 根
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右

**前序遍历（递归）**：

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

**前序遍历（栈实现）：**

class Solution { 
    public:
        vector<int> preorderTraversal(TreeNode* root) { 
            stack<TreeNode*> st;
            vector<int> result;
            st.push(root);
            while (!st.empty()) { 
                TreeNode* node = st.top();                      // 中
                st.pop();
                if (node != NULL) result.push_back(node->val);
                else continue;
                st.push(node->right);                           // 右
                st.push(node->left);                            // 左
            }
            return result;
        }
    };

**中序遍历（递归）**

void traversal(TreeNode* cur, vector<int>& vec) { 
            if (cur == NULL) return;
            traversal(cur->left, vec);  // 左
            vec.push_back(cur->val);    // 根
            traversal(cur->right, vec); // 右
        }

**中序遍历（栈）**  
在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

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

**后序遍历（递归）**

void traversal(TreeNode* cur, vector<int>& vec) { 
            if (cur == NULL) return;
            traversal(cur->left, vec);  // 左
            traversal(cur->right, vec); // 右
            vec.push_back(cur->val);    // 根
        }

**后序遍历（栈）**  
后序遍历只需要前序遍历的代码稍作修改就可以了。

class Solution { 
    public:
    
        vector<int> postorderTraversal(TreeNode* root) { 
            stack<TreeNode*> st;
            vector<int> result;
            st.push(root);
            while (!st.empty()) { 
                TreeNode* node = st.top();
                st.pop();
                if (node != NULL) result.push_back(node->val);
                else continue;
                st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序
                st.push(node->right);
            }
            reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
            return result;
        }
    };

**层序遍历（广度优先遍历）** \--利用队列实现

class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            queue<TreeNode*> que;
            if (root != NULL) que.push(root);
            vector<vector<int>> result;
            while (!que.empty()) { 
                int size = que.size();
                vector<int> vec;
                // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
                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;
        }
    };

[二叉树：层序遍历登场][Link 1] 里面的例题敲敲会。

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484713&idx=1&sn=2072608d432def7457fdfa27b73d8193&scene=21#wechat_redirect