四、二叉树-上（Binary tree）

文章目录

• 一、算法核心思想
• 二、算法模型
• • （一）回溯
  • • 1.[104.二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)
    • • （1）思路
      • （2）代码
      • （3）复杂度分析
    • 2.[144.二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/description/)
    • • （1）思路
      • （2）代码
      • （3）复杂度分析
    • 3.[543.二叉树的直径](https://leetcode.cn/problems/diameter-of-binary-tree/description/)
    • • （1）思路
      • （2）代码
      • （3）复杂度分析

一、算法核心思想

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分！
快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

二、算法模型

（一）回溯

1.104.二叉树的最大深度

（1）思路

如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为max(l,r)+1，而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

（2）代码

/** * 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 == nullptr) return 0;return max(maxDepth(root -> left),maxDepth(root -> right)) + 1;}};

（3）复杂度分析

• 时间复杂度：O(n），其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：O(height)，height表示二叉树的高度，递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

2.144.二叉树的前序遍历

（1）思路

（2）代码

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

（3）复杂度分析

• 时间复杂度：O(n）
• 空间复杂度：O(n)

3.543.二叉树的直径

（1）思路

（2）代码

/** * 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 res = 0;int diameterOfBinaryTree(TreeNode* root) { maxDepth(root);return res;}int maxDepth(TreeNode* root) {if (root == nullptr)return 0;int leftMax = maxDepth(root -> left);int rightMax = maxDepth(root -> right);int myDia = leftMax + rightMax;res = max(res,myDia);return 1 + max(leftMax,rightMax);}};

（3）复杂度分析

• 时间复杂度：O(n）
• 空间复杂度：O(n)