算法与数据结构学习笔记：二叉树

本文最后更新于：November 28, 2021 am

知识点

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

  • 以根访问顺序决定是什么遍历
  • 左子树都是优先右子树

前序遍历

例题：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    vector<int> preorderTraversal(TreeNode* root) {
       
        if(root==NULL)
            return ans;
		// 先访问根再访问左右
        ans.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return ans;

    }
};
非递归
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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
       vector<int> ans;
        if(root==NULL)
            return ans;
        stack<TreeNode*> st;
        TreeNode *cur=root;
        while(cur!=NULL||!st.empty())
        {
            while(cur!=NULL)
            {
                ans.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }
            cur=st.top();
            st.pop();
            cur=cur->right;

        }
        return ans;
       
    }
};

也可以这么写

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
       vector<int> ans;
        if(root==NULL)
            return ans;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            auto cur=st.top();
            st.pop();
            ans.push_back(cur->val);
            if(cur->right)
                st.push(cur->right);
            if(cur->left)
                st.push(cur->left);
        }

        return ans;       
    }
};

中序遍历

例题：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:   
    vector<int>ans;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==NULL)
            return ans;       
        inorderTraversal(root->left);
        ans.push_back(root->val);
        inorderTraversal(root->right);
        return ans;
       
    }
};

后序遍历：

例题：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==NULL)
            return ans;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        ans.push_back(root->val);
        return ans;

    }
};

分治法应用

先分别处理局部，再合并结果

适用场景

  • 快速排序
  • 归并排序
  • 二叉树相关问题

分治法模板

  • 递归返回条件
  • 分段处理
  • 合并结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ResultType traversal(TreeNode *root) {
    // nil or leaf
    if (!root) {
        // do something and return
    }

    // Divide
    auto left = traversal(root->left);
    auto right = traversal(root->right);

    // Conquer
    auto result = merge(left, right);

    return result;
}

典型示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// V2：通过分治法遍历二叉树
vector<int> preOrderTraversal(TreeNode *root) {
    return divideAndConquer(root);
}

vector<int> divideAndConquer(TreeNode *root) {
    vector<int> result;
    if (!root) {
        return result;
    }
    // 分治(Divide)
    auto left = divideAndConquer(root->left);
    auto right = divideAndConquer(root->right);
    // 合并结果(Conquer)
    result.push_back(root->val);
    result.insert(result.end(), left.begin(), left.end());
    result.insert(result.end(), right.begin(), right.end());
    return 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
36
37
38
39
template<typename T>
static void MergeSort(T arr[], int len) {
    auto tmp = new T[len];
    mergeSort(arr, 0, len - 1, tmp);
    delete[] tmp;
}

template<typename T>
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
    if (begin + 1 >= end) {
        return;
    }

    auto mid = begin + (end - begin) / 2;
    auto begin1 = begin;
    auto end1 = mid;
    auto begin2 = mid + 1;
    auto end2 = end;
    mergeSort(arr, begin1, end1, tmp);
    mergeSort(arr, begin2, end2, tmp);

    // merge two parts
    auto index = begin;
    while (begin1 <= end1 && begin2 <= end2) {
        tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
    }

    while (begin1 <= end1) {
        tmp[index++] = arr[begin1++];
    }

    while (begin2 <= end2) {
        tmp[index++] = arr[begin2++];
    }

    for (int i = begin; i <= end; ++i) {
        arr[i] = tmp[i];
    }
}

快速排序

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
template<typename T>
static void QuickSort(T arr[], int len) {
    quickSort(arr, 0, len - 1);
}

template<typename T>
static void quickSort(T arr[], int begin, int end) {
    if (begin >= end) {
        return;
    }
    auto pivot = partition(arr, begin, end);
    quickSort(arr, begin, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

template<typename T>
static int partition(T arr[], int begin, int end) {
    auto base = arr[end];
    auto lessInsert = begin;
    for (int i = begin; i < end; ++i) {
        if (arr[i] < base) {
            swap(arr[lessInsert++], arr[i]);
        }
    }
    swap(arr[lessInsert], arr[end]);
    return lessInsert;
}

常见题目示例

104. 二叉树的最大深度
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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;

        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        if(left>right)
             return left+1;
        else
            return right+1;
        
        
    }
};
110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3
/
9 20
/
15 7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1

/
2 2
/
3 3
/
4 4
返回 false 。

从底至顶

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

注意

一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(maxDepth(root)==-1)
        {
            return false;
        }
        return true;

        
    }
    int maxDepth(TreeNode *root)
    {
        if(root==NULL)
        {
            return 0;
        }
      int left=maxDepth(root->left);
      int right=maxDepth(root->right);
      if(left==-1||right==-1||left-right>1||right-left>1)
      {
          return -1;
      }
      if(left>right)
      {
          return left+1;
      }
      return right+1;
    }
};
124. 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

1

/
2 3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

-10
/
9 20
/
15 7

输出: 42

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res=INT_MIN;
        helper(root,res);
        return res;
    }
    int helper(TreeNode*root,int &val)
    {
        if(root==NULL)
         return 0;
        int left=max(0,helper(root->left,val));
        int right=max(0,helper(root->right,val));
        int lmr=root->val+left+right;
        int ret=root->val+max(left,right);
        val=max(val,max(lmr,ret));
        return ret;



    }
};
236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

img

示例 1:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)
            return root;
         // 相等 直接返回root节点即可
        if(root==p||root==q)
            return root;
        auto left=lowestCommonAncestor(root->left,p,q);
        auto right=lowestCommonAncestor(root->right,p,q);
          // 左右两边都不为空，则根节点为祖先
        if(left!=NULL&&right!=NULL)
            return root;
        if(left!=NULL)
            return left;
        if(right!=NULL)
            return right;
        return NULL;
        
    }
};

BFS 层次应用

102. 二叉树的层序遍历

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

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
           int currentLevelSize=q.size();
           vector<int> level;
           for(int i=0;i<currentLevelSize;i++)
           {
                auto cur=q.front();
                level.push_back(cur->val);
                q.pop();
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);               
           }
           res.push_back(level);
        }
        return res;
        
    }
};
107. 二叉树的层次遍历 II

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

思路：在层级遍历的基础上，翻转一下结果即可

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            int curLevelSize=q.size();
            vector<int> curLevel;
            for(int i=0;i<curLevelSize;i++)
            {
                auto cur=q.front();
                q.pop();
                curLevel.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)            
                    q.push(cur->right);
                
            }
            res.push_back(curLevel);
            
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
103. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3
/
9 20
/
15 7
返回锯齿形层次遍历如下：

[
[3],
[20,9],
[15,7]
]

思路：特定层结果翻转即可

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        bool toggle=false;
        while(!q.empty())
        {
            int curLevelSize=q.size();
            vector<int> curLevel;            
            for(int i=0;i<curLevelSize;i++)
            {
                auto cur=q.front();
                q.pop();
                curLevel.push_back(cur->val);
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);                               

            }
            if(toggle)
            {
                reverse(curLevel.begin(),curLevel.end());
            }               
            toggle=!toggle;
            res.push_back(curLevel);
        }
        return res;
    }
};

二叉搜索树应用

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

中序遍历
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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root==NULL)
            return true;
        vector<int>res;
        inOrder(root,res);
        for(int i=0;i<res.size()-1;i++)
        {
            if(res[i]>=res[i+1])
                return false;
        }
        return true;

        
    }
    void inOrder(TreeNode*root,vector<int> &res)
    {
        if(root==NULL)
            return;
        inOrder(root->left,res);
        res.push_back(root->val);
        inOrder(root->right,res);
    }
};
701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

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
/**
 * 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* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
            return new TreeNode(val);
        if(root->val<val)
        {
            root->right=insertIntoBST(root->right,val);
        }
        else
        {
            root->left=insertIntoBST(root->left,val);
        }
        return root;
        
    }
};