二叉树

1、求根节点到叶子节点数字之和

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）
image.png
image.png

我的解法：使用中序遍历，为什么使用中序遍历？
第一、直观印象，回溯算法我惯用中序遍历
第二、对于本题，我没有记录访问过的路径 vector<int> path，我是在叶子节点处对数值进行累加的，所以必须要用中序遍历的方式。

废话不多说，C++完整代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int sum = 0;        // 结果
  15.     void traversal(TreeNode* root, int curSum){
  16.         // 中
  17.         if(root->left == nullptr && root->right == nullptr){
  18.             sum += curSum;
  19.             return;
  20.         }
  21.         // 左
  22.         if(root->left) traversal(root->left, (curSum * 10 + root->left->val));        // 回溯，藏在了参数里
  23.         // 右
  24.         if(root->right) traversal(root->right, curSum * 10 + root->right->val);        // 回溯，藏在了参数里
  26.         return;
  27.     }
  29.     int sumNumbers(TreeNode* root) {
  30.         traversal(root, root->val);
  31.         return sum;
  32.     }
  33. };

上面的代码，需要对回溯有一定的理解，看不懂的话可以看下面的代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int result;
  15.     vector<int> path;
  16.     // 自定义函数，将vector转成int
  17.     int vectorToInt(const vector<int>& path){
  18.         int sum = 0;
  19.         for(int i = 0; i < path.size(); i++){
  20.             sum = sum * 10 + path[i];
  21.         }
  22.         return sum;
  23.     }
  25.     // 自定义函数，实现对二叉树的回溯
  26.     void backtracking(TreeNode* root){
  27.         // 中
  28.         if(!root->left && !root->right){
  29.             result += vectorToInt(path);
  30.             return;
  31.         }
  32.         // 左
  33.         if(root->left){
  34.             path.push_back(root->left->val);    // 处理节点
  35.             backtracking(root->left);           // 递归
  36.             path.pop_back();                    // 回溯，撤销上一步的操作
  37.         }
  38.         // 右
  39.         if(root->right){
  40.             path.push_back(root->right->val);   // 处理节点
  41.             backtracking(root->right);          // 递归
  42.             path.pop_back();                    // 回溯，撤销上一步的操作
  43.         }
  44.         return;
  45.     }
  48.     int sumNumbers(TreeNode* root) {
  49.         if(root == nullptr) return 0;
  50.         path.clear();
  51.         result = 0;
  52.         path.push_back(root->val);
  53.         backtracking(root);
  54.         return result;
  55.     }
  56. };

Java代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int result = 0;
  18.     public void traversal(TreeNode root, int curSum){
  19.         // 中，处理节点
  20.         if(root.left == null && root.right == null){
  21.             result += curSum;
  22.             return;
  23.         }
  24.         // 左(空节点不递归)
  25.         if(root.left != null) traversal(root.left, curSum * 10 + root.left.val);
  26.         // 右(空姐点不递归)
  27.         if(root.right != null) traversal(root.right, curSum * 10 + root.right.val);
  29.         return;
  30.     }
  32.     public int sumNumbers(TreeNode root) {
  33.         traversal(root, root.val);
  34.         return result;
  35.     }
  36. }

2、路径总和 II

113. 路径总和 II - 力扣（LeetCode）
image.png
image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<vector<int>> result;
  15.     vector<int> path;
  16.     void backtracking(TreeNode* root, int targetSum){
  17.         if(!root->left && !root->right){
  18.             if(getPathSum(path) == targetSum){
  19.                 result.push_back(path);
  20.                 return;
  21.             }
  22.         }
  23.         if(root->left){
  24.             path.push_back(root->left->val);
  25.             backtracking(root->left, targetSum);
  26.             path.pop_back();
  27.         }
  28.         if(root->right){
  29.             path.push_back(root->right->val);
  30.             backtracking(root->right, targetSum);
  31.             path.pop_back();
  32.         }
  33.         return;
  34.     }
  36.     int getPathSum(vector<int>& path){
  37.         int sum = 0;
  38.         for(int i = 0; i < path.size(); i++){
  39.             sum += path[i];
  40.         }
  41.         return sum;
  42.     }
  44.     vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
  45.         result.clear();
  46.         path.clear();
  47.         if(root == nullptr) return result;
  48.         path.push_back(root->val);
  49.         backtracking(root, targetSum);
  50.         return result;
  51.     }
  52. };

Java代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     List<List<Integer>> result = new ArrayList<>();
  18.     List<Integer> path = new ArrayList<>();
  19.     // 自定义函数，回溯二叉树
  20.     public void backtracking(TreeNode root, int targetSum){
  21.         if(root.left == null && root.right == null){
  22.             if(getPathSum(path) == targetSum){
  23.                 result.add(new ArrayList<>(path));
  24.             }
  25.             return;
  26.         }
  27.         if(root.left != null){
  28.             path.add(root.left.val);                // 添加元素
  29.             backtracking(root.left, targetSum);     // 递归
  30.             path.remove(path.size() - 1);           // 回溯
  31.         }
  32.         if(root.right != null){
  33.             path.add(root.right.val);
  34.             backtracking(root.right, targetSum);
  35.             path.remove(path.size() - 1);
  36.         }
  37.     }
  39.     // 自定义函数，对path求和
  40.     public int getPathSum(List<Integer> path){
  41.         int sum = 0;
  42.         for(int i = 0; i < path.size(); i++){
  43.             sum += path.get(i);
  44.         }
  45.         return sum;
  46.     }
  49.     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  50.         // result.removeAll(result);
  51.         // path.removeAll(path);
  52.         if(root == null) return result;
  53.         path.add(root.val);
  54.         backtracking(root, targetSum);
  55.         return result;
  56.     }
  57. }

3、路径总和

112. 路径总和 - 力扣（LeetCode）
image.png
image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool backtracking(TreeNode* root, int count){
  15.         if(!root->left && !root->right && count == 0) return true;      // 遇到叶子节点，并且计数为0
  16.         if(!root->left && !root->right) return false;                   // 遇到叶子节点直接返回
  18.         if(root->left){
  19.             if(backtracking(root->left, count - root->left->val)){
  20.                 return true;
  21.             }
  22.         }
  24.         if(root->right){
  25.             if(backtracking(root->right, count - root->right->val)){
  26.                 return true;
  27.             }
  28.         }
  30.         return false;
  31.     }
  33.     bool hasPathSum(TreeNode* root, int targetSum) {
  34.         if(root == nullptr) return false;
  35.         return backtracking(root, targetSum - root->val);
  36.     }
  37. };

Java代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     boolean flag = false;
  18.     public void backtracking(TreeNode root, int targetSum){
  19.         if(root.left == null && root.right == null){
  20.             if(targetSum == 0){
  21.                 flag = true;
  22.             }
  23.         }
  25.         if(root.left != null){
  26.             backtracking(root.left, targetSum - root.left.val);     // 回溯
  27.         }
  29.         if(root.right != null){
  30.             backtracking(root.right, targetSum - root.right.val);
  31.         }
  32.     }
  35.     public boolean hasPathSum(TreeNode root, int targetSum) {
  36.         if(root == null) return false;
  37.         backtracking(root, targetSum - root.val);
  38.         return flag;
  39.     }
  40. }

4、验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）
image.png
image.png

递归法

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> vec;
  15.     void backtracking(TreeNode* root){
  16.         if(root == nullptr){
  17.             return;
  18.         }
  19.         backtracking(root->left);
  20.         vec.push_back(root->val);
  21.         backtracking(root->right);
  22.     }
  24.     bool isValidBST(TreeNode* root) {
  25.         backtracking(root);
  26.         for(int i = 0; i < vec.size() - 1; i++){
  27.             if(vec[i] >= vec[i + 1]) return false;
  28.         }
  29.         return true;
  30.     }
  31. };

迭代法
方法一：
这道题可以使用 long long maxVal = LONG_MIN; 来记录上一次出现的最大的值，如果当前节点的值小于这个 maxVal，说明这不是一颗二叉搜索树。
代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool isValidBST(TreeNode* root) {
  15.         stack<TreeNode*> st;
  16.         st.push(root);
  17.         long long maxVal = LONG_MIN;
  18.         while(!st.empty()){
  19.             TreeNode* cur = st.top();
  20.             if(cur != nullptr){
  21.                 st.pop();
  22.                 if(cur->right) st.push(cur->right);     // 右
  23.                 st.push(cur);                           // 中
  24.                 st.push(nullptr);
  25.                 if(cur->left) st.push(cur->left);       // 左
  26.             }
  27.             else{
  28.                 st.pop();   // 弹出标记的节点 nullptr
  29.                 if(maxVal >= st.top()->val) return false;
  30.                 maxVal = maxVal > st.top()->val ? maxVal : st.top()->val;   // 更新maxVal的值
  31.                 st.pop();   // 弹出当前节点
  32.             }
  33.         }
  34.         return true;
  35.     }
  36. };

但是这种解法仍然存在不足，如果二叉树节点的数值最大比 long long 类型还大呢？这时候就溢出啦。

方法二：
使用pre 指针，指向上一次访问的节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     bool isValidBST(TreeNode* root) {
  15.         stack<TreeNode*> st;
  16.         st.push(root);
  17.         TreeNode* pre = nullptr;
  19.         while(!st.empty()){
  20.             TreeNode* cur = st.top();
  21.             if(cur != nullptr){
  22.                 st.pop();
  23.                 if(cur->right) st.push(cur->right);     // 右
  24.                 st.push(cur);                           // 中
  25.                 st.push(nullptr);       // 插入标志
  26.                 if(cur->left) st.push(cur->left);       // 左
  27.             }
  28.             else{
  29.                 st.pop();               // 弹出标记的节点 nullptr
  30.                 if(pre != nullptr && pre->val >= st.top()->val){
  31.                     return false;
  32.                 }
  33.                 pre = st.top();         // 记录前一个节点值
  34.                 st.pop();
  35.             }
  36.         }
  37.         return true;
  38.     }
  39. };

Java代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     List<Integer> list = new ArrayList<>();
  18.     void traversal(TreeNode root){
  19.         if(root == null){
  20.             return;
  21.         }
  22.         traversal(root.left);
  23.         list.add(root.val);
  24.         traversal(root.right);
  25.     }
  27.     public boolean isValidBST(TreeNode root) {
  28.         list.clear();
  29.         traversal(root);
  30.         for(int i = 0; i < list.size() - 1; i++){
  31.             if(list.get(i) >= list.get(i + 1)) return false;
  32.         }
  33.         return true;
  34.     }
  35. }
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean isValidBST(TreeNode root) {
  18.         Stack<TreeNode> st = new Stack<>();
  19.         st.push(root);
  20.         TreeNode pre = null;
  22.         while(!st.isEmpty()){
  23.             TreeNode cur = st.peek();
  24.             if(cur != null){
  25.                 st.pop();
  26.                 if(cur.right != null) st.push(cur.right);       // 右
  27.                 st.push(cur);                                   // 中
  28.                 st.push(null);      // 插入标志
  29.                 if(cur.left != null) st.push(cur.left);         // 左
  30.             } else{
  31.                 st.pop();
  32.                 if(pre != null && pre.val >= st.peek().val){
  33.                     return false;
  34.                 }
  35.                 pre = st.peek();
  36.                 st.pop();
  37.             }
  38.         }
  39.         return true;
  40.     }
  41. }

5、将有序数组转为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
image.png
image.png

题目中说要转换为一棵高度平衡二叉搜索树。这和转换为一棵普通二叉搜索树有什么差别呢？
其实这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取，所以想构成不平衡的二叉树是自找麻烦。
在二叉树：构造二叉树登场！(opens new window)和二叉树：构造一棵最大的二叉树(opens new window)中其实已经讲过了，如果根据数组构造一棵二叉树。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

C++完整代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* traversal(vector<int>& nums, int left, int right){
  15.         if(left > right){                                   // 如果区间元素与足以构成节点，即区间为空
  16.             return nullptr;
  17.         }
  19.         int middle = left + ((right - left) >> 1);          // BST对应数组的中间节点就是根节点
  20.         TreeNode* node = new TreeNode(nums[middle]);        // 构建根节点
  22.         node->left = traversal(nums, left, middle - 1);     // 递归左子树
  23.         node->right = traversal(nums, middle + 1, right);   // 递归右子树
  25.         return node;
  26.     }
  28.     TreeNode* sortedArrayToBST(vector<int>& nums) {
  29.         return traversal(nums, 0, nums.size() - 1);
  30.     }
  31. };

理解递归我觉得就可以了，迭代法的话，面试应该不会这么变态同时让写递归和迭代。

Java代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode buildBST(int[] nums, int left, int right){
  18.         if(left > right) return null;                   // 如果left>right，说明当前区间为null
  20.         int middle = left + ((right - left) >> 1);
  21.         TreeNode node = new TreeNode(nums[middle]);      // new一个节点
  23.         node.left = buildBST(nums, left, middle - 1);           // 递归左子树
  24.         node.right = buildBST(nums, middle + 1, right);         // 递归右子树
  26.         return node;
  27.     }
  29.     public TreeNode sortedArrayToBST(int[] nums) {
  30.         return buildBST(nums, 0, nums.length - 1);
  31.     }
  32. }

6、从中序与后续遍历构建二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
image.png
image.png

下面的代码，我不做解释，如果看不懂，请看这里 二刷代码随想录 - 二叉树 - 从中序与后序遍历构建二叉树

2、将二叉搜索树变平衡

1382. 将二叉搜索树变平衡 - 力扣（LeetCode）
image.png
image.png