数据结构之二叉树

二叉树遍历

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

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

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

注意点

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

前序递归

/**
 * 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> ve;
     vector<int> preorderTraversal(TreeNode* root) {
         if(root) {
             ve.push_back(root -> val);
             preorderTraversal(root -> left);
             preorderTraversal(root -> right);
         }
     return ve;
     }
 };

前序非递归（迭代法）

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ve;
        if(root == NULL)
            return ve;
        vector<TreeNode*> stk;
        stk.push_back(root);
        while(!stk.empty()){
            TreeNode* tmp = stk.back();
            stk.pop_back();
            ve.push_back(tmp -> val);
            if(tmp -> right){
                stk.push_back(tmp -> right);
            }
            if(tmp -> left){
                stk.push_back(tmp -> left);
            }
        }
    return ve;
    }
};

中序非递归（迭代法）

二叉树的中序遍历

/* 思路：每到一个节点 A，因为根的访问在中间，将 A 入vector。
 * 然后遍历左子树，接着访问 A，最后遍历右子树。
 * 在访问完 A 后，A 就可以出vector了。因为 A 和其左子树都已经访问完成。
 * 和前序类似
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<TreeNode*> ve;
        vector<int> v;
        TreeNode* rt = root;
        while(rt || !ve.empty()) {
            while(rt) {
                ve.push_back(rt);
                rt=rt->left;
            }
            rt=ve.back();
            ve.pop_back();
            v.push_back(rt->val);
            rt=rt->right;
        }
        return v;
    }
};

后序非递归（迭代法）

二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        vector<TreeNode*> stk;
        stk.push_back(root);
        while(!stk.empty()){
            TreeNode* tmp = stk.back();
            stk.pop_back();
            if(tmp!=nullptr){
                stk.push_back(tmp);
                stk.push_back(nullptr);
                if(tmp -> right) stk.push_back(tmp -> right);
                if(tmp -> left) stk.push_back(tmp -> left);
            }
            else{
                res.push_back(stk.back()->val);
                stk.pop_back();
            }
        }
        return res;
    }
};

注意点

核心就是：根节点必须在右节点弹出之后，再弹出

DFS 深度搜索-从上到下

二叉树的前序遍历

class Solution {
public:
    // 深度遍历，结果指针作为参数传入到函数内部
    void dfs(TreeNode* root, vector<int>* result){
        if(root){
            result -> push_back(root -> val);
            dfs(root -> left, result);
            dfs(root -> right, result);
        }
    }
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        dfs(root, &res);
        return res;
    }
};

这实际上就是递归的实现

DFS 深度搜索-从下向上（分治法）

二叉树的前序遍历

分治法模板

递归返回条件
分段处理
合并结果

Type traversal(TreeNode* root) {
    // NULL or leaf
    if(root == NULL) {
        // do something and return
    }

    // Divide
    Type left = traversal(root -> Left)
    Type right = traversal(root -> Right)

    // Conquer
    Type result = Merge from left and right

    return result
}

答案代码

class Solution {
public:
    vector<int> divideAndConquer(TreeNode* root){
        vector<int> result;
        if(root != NULL){
            vector<int> r_left = divideAndConquer(root -> left);
            vector<int> r_right = divideAndConquer(root -> right);
            result.push_back(root -> val);
            for(auto it : r_left){
                 result.push_back(it);
            }
            for(auto it : r_right){
                 result.push_back(it);
            }
        }
        return result;
    }
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        res = divideAndConquer(root);
        return res;
    }
};

注意点：

DFS 深度搜索（从上到下）和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

BFS 层次遍历

二叉树的层次遍历 II

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

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

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> result;
        if(!root){
            return result;
        }
        q.push(root);
        while(!q.empty()){
            vector<int> ve;
            int nums = q.size();
            for(int i = 0; i < nums; i++){
                TreeNode* tmp = q.front();
                q.pop();
                ve.push_back(tmp->val);
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right){
                    q.push(tmp->right);
                }
            }
            result.insert(result.begin(), ve);
        }
        return result;
    }
};

分治法应用

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

适用场景

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

归并排序

归并和快排

归并排序是典型分治思想的代表——首先把原问题分解为两个或多个子问题，然后求解子问题的解，最后使用子问题的解来构造出原问题的解。
对于归并排序，给定一个待排序的数组，首先把该数组划分为两个子数组，然后对子数组进行排序（递归调用归并排序），最后对两个有序的子数组进行合并，使合并之后的数组为有序状态。
让我们想想，把一个数组不断地划分为子数组，不断地划分……,不断地划分……., 最后停止了划分不下去了。此时子数组的元素有一个，它们本身就是有序的。接下来，我们就需要执行合并过程，不断地一层层向上合并，…….., 直到原数组。通过这个过程就会发现，归并排序的核心在于合并有序的子数组，而不是对子数组进行排序，因为最底层的子数组本身就是有序的，上一层子数组如果想要变成有序的，通过合并底层有序的子数组就可以得到，最终我们使原数组变成了有序的，从而完成了排序操作。

归并排序是用分治思想，时间复杂度为O(NlogN)。分治模式在每一层递归上有三个步骤：

分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果。

#include <cstring>
#include <iostream>
typedef bool (*CompareFunc)(int, int);

// 下面函数实现合并功能，输入三个下标参数表示了两个子数组, :[nStart_, nMiddle)和[nMiddle, nEnd)
void Merge(int array[], int nStart_, int nMiddle_, int nEnd_,
           CompareFunc comp) {
  if (array == nullptr || nStart_ >= nMiddle_ || nMiddle_ >= nEnd_) return;

  // 建立一个临时数组存放中间数据
  int _nIndex = 0;
  int* _pTempArray = new int[nEnd_ - nStart_];

  // 对两个子数组进行合并
  int _nStartChange = nStart_;
  int _nMiddleChange = nMiddle_;
  while (_nStartChange < nMiddle_ && _nMiddleChange < nEnd_) {
    // 此处的if中比较语句的安排可以保持稳定排序的特性。
    if (comp(array[_nMiddleChange], array[_nStartChange])) {
      _pTempArray[_nIndex] = array[_nMiddleChange];
      ++_nMiddleChange;
    } else {
      _pTempArray[_nIndex] = array[_nStartChange];
      ++_nStartChange;
    }
    ++_nIndex;
  }

  // 把不为空的子数组的元素追加到临时数
  if (_nStartChange < nMiddle_) {
    memcpy(_pTempArray + _nIndex, array + _nStartChange,
           sizeof(int) * (nMiddle_ - _nStartChange));
  } else if (_nMiddleChange < nEnd_) {
    memcpy(_pTempArray + _nIndex, array + _nMiddleChange,
           sizeof(int) * (nEnd_ - _nMiddleChange));
  } else {
    /* do noting */
  }

  // 数据交换
  memcpy(array + nStart_, _pTempArray, sizeof(int) * (nEnd_ - nStart_));

  delete[] _pTempArray;
  _pTempArray = nullptr;
}

// 归并排序功能实现函数
void MergeSort(int array[], int nStart_, int nEnd_, CompareFunc comp) {
  // 数组指针为空，或者数组内的个数少于等于1个时，直接返回。
  if (nullptr == array || (nEnd_ - nStart_) <= 1) return;

  // 划分为两个子数组并递归调用自身进行排序
  int _nMiddle = (nStart_ + nEnd_) / 2;
  MergeSort(array, nStart_, _nMiddle, comp);
  MergeSort(array, _nMiddle, nEnd_, comp);

  // 合并排序完成的子数组
  Merge(array, nStart_, _nMiddle, nEnd_, comp);
}

// 比较函数
bool less(int lhs, int rhs) { return lhs < rhs; }
bool large(int lhs, int rhs) { return lhs > rhs; }

// 打印数组函数
void PrintArray(int array[], int nLength_) {
  if (nullptr == array || nLength_ <= 0) return;

  for (int i = 0; i < nLength_; ++i) {
    std::cout << array[i] << " ";
  }
  std::cout << std::endl;
}

/***************    main.c     *********************/
int main(int argc, char* argv[]) {
  // 测试
  int array[10] = {1, -1, 1, 5, -5, -1, -1, 3, -4, -2};
  MergeSort(array, 0, 9, large);
  PrintArray(array, 10);
  return 0;
}

快速排序

快速排序作为20世纪十大算法之一，我们这些玩编程的好像没有理由不去学习它。快速排序是冒泡排序的升级版。

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。可参考这位大佬

快速排序图解

#include <iostream>

typedef bool (*CompareFunc)(int, int);

// 比较函数
bool less(int lhs, int rhs) { return lhs <= rhs; }   // 从小到大
bool large(int lhs, int rhs) { return lhs >= rhs; }  // 从大到小

void quickSort(int left, int right, int arr[], CompareFunc comp) {
  // 递归边界条件
  if (left >= right) return;
  int i, j, base, temp;
  i = left, j = right;
  base = arr[left];  //取最左边的数为基准数
  while (i < j) {
    while (comp(base, arr[j]) && i < j) j--;
    while (comp(arr[i], base) && i < j) i++;
    if (i < j) {
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  //基准数归位
  arr[left] = arr[i];
  arr[i] = base;
  quickSort(left, i - 1, arr, comp);   //递归左边
  quickSort(i + 1, right, arr, comp);  //递归右边
}

// 打印数组函数
void PrintArray(int array[], int nLength_) {
  if (nullptr == array || nLength_ <= 0) return;

  for (int i = 0; i < nLength_; ++i) {
    std::cout << array[i] << " ";
  }
  std::cout << std::endl;
}

int main(int argc, char* argv[]) {
  // 测试
  int array[10] = {1, -1, 1, 5, -5, -1, -1, 3, -4, -2};
  quickSort(0, 9, array, less);
  PrintArray(array, 10);
  quickSort(0, 9, array, large);
  PrintArray(array, 10);
  return 0;
}

注意点：

快排由于是原地交换所以没有合并过程传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃

常见题目示例

二叉树的最大深度

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

思路：分治法

/**
 * 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) return 0;
        if(!root -> left && !root -> right) return 1;
        // divide：分左右子树分别计算
        int left = maxDepth(root -> left);
        int right = maxDepth(root -> right);
        // conquer：合并左右子树结果
        return left > right ? left + 1 : right + 1;
    }
};

平衡二叉树

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

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

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(maxDepth(root) == -1) {
            return false;
        }
        return true;
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root -> left && !root -> right) return 1;
        int left = maxDepth(root -> left);
        int right = maxDepth(root -> right);
        // 为什么返回-1呢？因为高度不可能为负数
        if(abs(left - right) > 1 || left == -1 || right == -1) {
            return -1;
        }
        return left > right ? left + 1 : right + 1;
    }
};

注意

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

二叉树中的最大路径和

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

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可

class Solution {
public:
    struct ResultType {
        int SinglePath; // 保存单边最大值
        int MaxPath;    // 保存最大值（单边或者两个单边+根的值）
    };
    ResultType helper(TreeNode* root) {
        if(root == NULL) {
            return {0,-(1 << 10)};
        }
        // Divide
        ResultType left = helper(root -> left);
        ResultType right = helper(root -> right);

        // Conquer
        ResultType result;
        // 求单边最大值
        if(left.SinglePath > right.SinglePath) {
            result.SinglePath = std::max(left.SinglePath + root -> val, 0);
        } else {
            result.SinglePath = std::max(right.SinglePath + root -> val, 0);
        }
        // 求两边加根最大值
        int tempMax = std::max(right.MaxPath, left.MaxPath);
        result.MaxPath = std::max(tempMax, left.SinglePath + right.SinglePath + root -> val);
        return result;
    }
    int maxPathSum(TreeNode* root) {
        ResultType result = helper(root);
        return result.MaxPath;
    }
};

二叉树的最近公共祖先

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

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 相等 直接返回root节点即可
        if(root == NULL || root == p || root == q) {
            return root;
        }

        // Divide
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);

        // Conquer
        // 左右两边都不为空，则根节点为祖先
        if(left != NULL && right != NULL) {
            return root;
        }
        if(left != NULL) {
            return left;
        }
        if(right != NULL) {
            return right;
        }
        return NULL;
    }
};

BFS 层次应用

二叉树的层序遍历

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

思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）。(和之前的二叉树的层次遍历 II类似)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> result;
        if(!root){
            return result;
        }
        q.push(root);
        while(!q.empty()){
            vector<int> ve;
            int nums = q.size();
            for(int i = 0; i < nums; i++){
                TreeNode* tmp = q.front();
                q.pop();
                ve.push_back(tmp->val);
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right){
                    q.push(tmp->right);
                }
            }
            result.push_back(ve);
        }
        return result;
    }
};

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

思路：在层次遍历的基础上加个下一层反向

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> result;
        if(!root){
            return result;
        }
        q.push(root);
        bool reverse_flag = false;
        while(!q.empty()){
            vector<int> ve;
            int nums = q.size();
            for(int i = 0; i < nums; i++){
                TreeNode* tmp = q.front();
                q.pop();
                ve.push_back(tmp->val);
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right){
                    q.push(tmp->right);
                }
            }
            if(reverse_flag) {
                std::reverse(ve.begin(), ve.end());
                reverse_flag = false;
            }
            else {
                reverse_flag = true;
            }
            result.push_back(ve);
        }
        return result;
    }
};

二叉搜索树应用

验证二叉搜索树

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

思路 1：递归

思路 2：中序遍历，检查结果列表是否已经有序

思路 3：分治法，判断左 MAX < 根 < 右 MIN

// v1
class Solution {
public:
    bool isBSTUtil(TreeNode* root, long min, long max) {
        if(root == NULL)
            return true;
        if(root->val <= min || root->val >= max)
            return false;
        return isBSTUtil(root->left, min, root->val) && isBSTUtil(root->right, root->val, max);
    }
    bool isValidBST(TreeNode* root) {
        long v_min = LONG_MIN, v_max = LONG_MAX;
        return isBSTUtil(root, v_min, v_max);
    }
};

// v2
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL) {
            return true;
        }
        vector<int> result;
        inOrder(root, &result);
        // 按左、根、右排列进行比较，左大于根或者根大于右则肯定不是平衡二叉树
        for(int i = 0; i < result.size() - 1; i++) {
            if(result[i] >= result[i + 1]) {
                return false;
            }
        }
        return true;
    }
    // 分别将左节点和右节点放入result
    void inOrder(TreeNode* root, vector<int>* result) {
        if(root == NULL) {
            return;
        }
        inOrder(root -> left, result);
        result -> push_back(root -> val);
        inOrder(root -> right, result);
    }
};

// v3
class Solution {
public:
    struct ResultType {
        bool IsValid;
        // 记录左右两边最大最小值，和根节点进行比较
        TreeNode* Max;
        TreeNode* Min;
    };
    bool isValidBST(TreeNode* root) {
        ResultType result = helper(root);
        return result.IsValid;
    }
    ResultType helper(TreeNode* root) {
        ResultType result = {};
        if(root == NULL) {
            result.IsValid = true;
            return result;
        }
        ResultType left = helper(root -> left);
        ResultType right = helper(root -> right);
        if(!left.IsValid || !right.IsValid) {
            result.IsValid = false;
            return result;
        }
        if(left.Max != NULL && (left.Max -> val) >= (root -> val)) {
            result.IsValid = false;
            return result;
        }
        if(right.Min != NULL && right.Min -> val <= root -> val) {
            result.IsValid = false;
            return result;
        }
        result.IsValid = true;
        // 如果左边还有更小的3，就用更小的节点，不用4
        //  5
        // / \
        // 1   4
        //    / \
        //   3   6
        result.Min = root;
        if(left.Min != NULL) {
            result.Min = left.Min;
        }
        result.Max = root;
        if(right.Max != NULL) {
            result.Max = right.Max;
        }
        return result;
    }
};

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。

思路：找到最后一个叶子节点满足插入条件即可

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) {
            return new TreeNode(val);
        }
        if(root -> val > val) {
            root -> left = insertIntoBST(root -> left, val);
        }
        else {
            root ->right = insertIntoBST(root -> right, val);
        }
        return root;
    }
};