字数统计: 4.3k字   |   阅读时长: 20分

二叉树 (1)

基础篇

  • 满二叉树:如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。也可以说深度为 k ，有2k -1个节点的二叉树。

  • 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2 (h -1) 个节点。之前学过的优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

  • 二叉搜索树:二叉搜索树是一个有序树, 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树

  • 二叉平衡搜索树: 又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 C++ 中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

  • 红黑树：红黑树是一种二叉平衡搜索树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树，但是都是二叉搜索树。

    进阶：Morris遍历

    神级遍历——morris - 知乎 (zhihu.com)

二叉树既可以链式存储, 也可以顺序存储。

顺序存储如果父节点的数组下标是i，那么它的左孩子就是i * 2 + 1,右孩子就是i * 2 + 2 。

二叉树的遍历方式

二叉树主要有两种遍历方式：

  • 深度优先遍历：先往深走，遇到叶子节点再往回走。

  • 广度优先遍历：一层一层的去遍历。

  • 深度优先遍历:前序遍历（递归法，迭代法）;中序遍历（递归法，迭代法）;后序遍历（递归法，迭代法）, 主要借助栈通过递归的方式实现。

  • 广度优先遍历:层次遍历（迭代法）, 通过队列以非递归的方式实现。

这里前中后，其实指的就是中间节点的遍历顺序, 前序遍历：中左右; 中序遍历：左中右; 后序遍历：左右中

链式存储二叉树的存储方式:

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

144. 二叉树的前序遍历
二叉树的前序, 中序, 和后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 traversal (TreeNode *cur, vector <int> &vec)
    {
        if(cur == NULL) return; //只能用if, while会报超时
        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;
    }
};

中序和后续就是把traversal函数的顺序换了一下, 原理都是一样的, 这种方法是递归解法。

144. 二叉树的前序遍历
迭代解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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) {
        stack <TreeNode*> st;  //定义一个结点类型的栈
        vector <int> result;
        if(root == NULL)
        return result;
        st.push(root);
        while(!st.empty())
        {
            TreeNode *Node = st.top();
            st.pop();
            result.push_back(Node->val);
            if(Node->right != NULL) st.push(Node->right);
            if(Node->left != NULL) st.push(Node->left); //遍历结点和输出到数组中可以同步进行
        }
        return result;
    }
};


思路：首先将根节点入栈然后弹出，将根节点输出到result数组作为结果。然后分别访问右子树和左子树，将栈顶元素（也就是这一层的左子树弹出，然后将这个结点的右子树和左子树入栈，依次类推…）

考虑前序遍历是中左右, 后序遍历是左右中. 因此可以先将左右迭代的顺序颠倒变成中右左, 然后再通过翻转数组变成左右中。

翻转可以用reverse函数:

1
reverse(result.begin(), result.end());

中序遍历与这两个的思路不一样, 中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序（堆栈）和访问顺序（输出的result数组）是不一致的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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> result;
        TreeNode *cur = root;
        while(cur != NULL || !st.empty())
        {
            if(cur != NULL)
            {
                st.push(cur);
                cur = cur->left; //将左孩子都压入栈,直到为空
            }
            else //堆栈不为空
            {
                cur = st.top();//按顺序依次是左,中，右
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;//当cur->right没有元素时cur为空，继续pop数据
            }
        }
        return result;
    }
};

思路: 先通过指针访问到最左边的结点, 一直入栈直到左边没有元素了。然后返回栈的前一个结点, 判断其是否有右孩子, 没有的话且非空就继续pop, 如果有右孩子就将指针指向右孩子,由此实现了左中右的遍历。

  • 二叉树的统一迭代法:

由于中序遍历无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况，因此常规的迭代方法不统一。

可以采用下面的方法实现统一迭代，即

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。具体方法就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记，这种方法也可以叫做标记法。

中序统一迭代法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top(); //把该层的左孩子弹出,避免重复操作
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

先序遍历和后序遍历也是相同的道理，只是需要改变一下入栈的顺序。

二叉树的层序遍历：

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> result;
        queue <TreeNode*> que;
        if(root != NULL)
        que.push(root);
        while(!que.empty())
        {
            vector <int> vec;
            int 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;		//result存的是每一层的数据
    }
};

107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

跟前面的思路一样就是最后将result翻转

1
reverse(result.begin(), result.end());

199. 二叉树的右视图 - 力扣（LeetCode） (leetcode-cn.com)

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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> rightSideView(TreeNode* root) {
        queue <TreeNode*> que;
        if(root != nullptr) que.push(root);
        vector <int> result;
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode *node = que.front();
                que.pop();
                if(i == size - 1) result.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result; 
    }
};

637. 二叉树的层平均值 - 力扣（LeetCode） (leetcode-cn.com)

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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<double> averageOfLevels(TreeNode* root) {
        queue <TreeNode*> que;
        vector <double> result;
        if(root != nullptr) que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            double sum = 0;
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                sum = sum + node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(sum/size);
        }
        return result;
    }
};

429. N 叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children; //变成多节点, 也就是对应多子树

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector <vector <int>> result;
        queue <Node*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector <int> vec;
            for(int i = 0; i < size; i++)
            {
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for(int j = 0; j < node->children.size(); j++)
                {
                    if(node->children[j]) que.push(node->children[j]);
                }
            }
            result.push_back(vec);
        }
        return result;
    }
};

与二叉树的遍历原理都是一样的，就是两个子节点变成了多个子节点用vector存储。

515. 在每个树行中找最大值 - 力扣（LeetCode） (leetcode-cn.com)

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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> largestValues(TreeNode* root) {
        vector <int> result;
        queue <TreeNode*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            int max = INT_MIN;
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if(node->val > max) max = node->val;
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
            result.push_back(max);
        }
        return result;
    }
};

注意INT_MIN是INT里的最小值，也就是-231；

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode） (leetcode-cn.com)

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue <Node*> que;
        if(root != NULL) que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            Node* node;
            for(int i = 0; i < size; i++)
            {
                node = que.front();
                que.pop();
                if(que.front() != nullptr)
                node->next = que.front();
                if(node->left != nullptr) que.push(node->left);
                if(node->right != nullptr) que.push(node->right);
            }
            node->next = NULL;
        }
        return root;
    }
};

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode） (leetcode-cn.com)

将上一题拓展到非完全二叉树, 没有变化。

104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com)

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int depth = 0;
        queue <TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty())
        {
            depth++;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
        }
        return depth;
    }
};

一个层序遍历就完事了, 很简单。

111. 二叉树的最小深度 - 力扣（LeetCode） (leetcode-cn.com)

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int depth = 0;
        queue <TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty())
        {
            depth++;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
                if(node->left == NULL && node->right == NULL)
                return depth; 
            }
        }
        return depth;
    }
};

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

226. 翻转二叉树 - 力扣（LeetCode） (leetcode-cn.com)

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

递归法，迭代法，层序遍历法都能实现（除中序），核心就是访问时将两个子树交换。

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

迭代法：先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

层序遍历：（广度优先搜索）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊