树型结构算法 | Automannn的学习园地

# 二叉树

# 二叉树的前序遍历

问题描述：给定二叉树的根节点root,求前序遍历列表
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        doPreorderTraversal(root,result);
        return result;
    }
    
    void doPreorderTraversal(TreeNode* node,vector<int>& result){
        if(!node){
            return;
        }else{
            result.push_back(node->val);
            doPreorderTraversal(node->left,result);
            doPreorderTraversal(node->right,result);
        }
    }
};

关键点
- 递归调用，无论问题多么复杂，必须先找到出栈条件
- 前序遍历的节点顺序为根左右
- 不管是前序，中序，还是后续遍历，递归函数执行时，始终只能访问根，只是访问的根相较于上层递归方法时，作为了它的左孩子或者右孩子
- 递归函数，可用参数实现各级递归的沟通功能

# 二叉树的后序遍历

问题描述：通过二叉树的根节点root,返回后序遍历列表
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        doPostorderTraversal(root,result);
        return result;
    }

    void doPostorderTraversal(TreeNode* node,vector<int>& result){
        if(!node){
            return;
        }else{
            doPostorderTraversal(node->left,result);
            doPostorderTraversal(node->right,result);
            result.push_back(node->val);
        }
    }
};

关键点
- 判断最终访问的根节点与上层递归方法的关系时，要看到最深的节点，同时递归前进方向联系起来看
- 后续遍历的序列为:左右根

# 二叉树的中序遍历

问题描述: 通过二叉树的根节点root,返回中序遍历列表
力扣位置 (opens new window)
题解

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        doInorderTraversal(root,result);
        return result;
    }

    void doInorderTraversal(TreeNode* node,vector<int>& result){
        if(!node){
            return;
        }else{
            doInorderTraversal(node->left,result);
            result.push_back(node->val);
            doInorderTraversal(node->right,result);
        }
    }
};

关键点
- 中序遍历序列为:左根右
- 特别容易与前序遍历搞混

# 二叉树的层序遍历

问题描述：通过二叉树根节点root,返回层序遍历序列
力扣位置 (opens new window)
题解

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

                if(tmp.right){
                    que.push(*tmp.right);
                }
                
                
            }
            result.push_back(tmp_que);
        }
        return result;
    }
};

关键点
- 队列需要边进边出，进出需要满足特定的条件
- 遍历完成的条件是队列为空
- 使用队列后，不能再用递归的思路

# 二叉树翻转

问题描述: 给定二叉树根节点root,返回翻转后的二叉树(左右孩子交换);
力扣位置 (opens new window)
题解

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root){
            swap(root,root->left,root->right);
            invertTree(root->left);
            invertTree(root->right);
        }
        return root;
    }

    void swap(TreeNode* root,TreeNode* left,TreeNode* right){
        root->left = right;
        root->right = left;
    }
};

关键点
- 树操作中，主要涉及到遍历
- 该题需要使用前序遍历翻转，因为不会影响后续操作
- 中序遍历，后续遍历，翻转的时候，会因为递归回溯相互影响，导致翻转结果异常

# 对称二叉树

问题描述：给定二叉树的根节点root,判断该二叉树是否轴对称;
力扣位置 (opens new window)
题解

class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right){
        // xxx: 当前层次处理 (简单)
        if(left==NULL&&right!= NULL)return false;
        else if(left!=NULL&& right==NULL) return false;
        else if(left==NULL && right == NULL) return true;
        else if (left->val != right->val ) return false;
        
        //处理更深的层次 (难)
        bool outside = compare(left->left,right->right);
        bool inside = compare(left->right,right->left);
        bool isSame = outside && inside;
        
        return isSame;
    }

    bool isSymmetric(TreeNode* root) {
        if(root == NULL)return true;

        return compare(root->left,root->right);
    }
};

关键点
- 使用了从上到下的迭代法
- 递归深入与回溯配合完成业务;

# 二叉树的最大深度

问题描述: 给定一个二叉树，查找其最大深度
力扣位置 (opens new window)
题解

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        int depth=0;
        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty()){
            int size = que.size();
            depth++;

            for(int i=0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return depth;
    }

};

关键点
- 层序遍历可以很好的处理树深度问题
- 结合双层循环，可实现每一层的操作划分

# 二叉树的最小深度

问题描述: 给定一个二叉树，找出其最小深度
力扣位置 (opens new window)
题解

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;

        int depth=0;
        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty()){
            int size = que.size();
            depth++;
            for(int i=0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();

                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                if(!node->left && !node->right){
                    return depth;
                }
            }
        }
        return depth;
    }
};

关键点
- 树深度问题，采用层序遍历解决
- 层序遍历时，出现的第一个叶子节点，一定是最小深度

# 完全二叉树的节点个数

问题描述: 给定一个完全二叉树的根节点root,求该树的节点个数
力扣位置 (opens new window)
题解

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

关键点
- 遍历计数即可，既可以采用层序遍历，也可采用深度遍历

# 平衡二叉树

问题描述: 给定一个二叉树，判断其是否为高度平衡的二叉树；
力扣位置 (opens new window)
题解

class Solution {
public:
    int getHeight(TreeNode* node){
        if(node==NULL){
            return 0;
        }
        int leftHeight=getHeight(node->left);
        if(leftHeight==-1) return -1;
        int rightHeight = getHeight(node->right);
        if(rightHeight==-1) return -1;
        return abs(leftHeight-rightHeight)>1?-1:1+max(leftHeight,rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root)==-1?false:true;
    }
};

关键点
- 使用了中序遍历
- 迭代函数的返回值为回溯的深度，本质上为叶节点到根节点的距离
- 使用了数学辅助函数：绝对值abs(), 最大值max()
- -1表示判定失败

# 二叉树的所有路径

问题描述: 给定二叉树根节点root,按任意顺序返回根节点到叶节点的路径;
力扣位置 (opens new window)
题解

class Solution {
private:
    void traversal(TreeNode* cur,vector<int>& path,vector<string>& result){
        path.push_back(cur->val);
        if(cur->left ==NULL && cur->right==NULL){
            string sPath;
            for(int i=0;i<path.size()-1;i++){
                sPath += to_string(path[i]);
                sPath +="->";
            }
            sPath += to_string(path[path.size()-1]);
            result.push_back(sPath);
        }
        if(cur->left){
            traversal(cur->left,path,result);
            path.pop_back();
        }
        if(cur->right){
            traversal(cur->right,path,result);
            path.pop_back();
        }

    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(root==NULL) return result;
        traversal(root,path,result);
        return result;
    }
};

关键点
- 使用了先序遍历
- 使用api方法to_string()
- 借助深入与回溯，实现非叶节点逻辑结构的复用
- 收集路径，在叶结点处完成

# 左叶子之和

问题描述: 给定二叉树的根节点root,返回所有左叶子节点之和。
力扣位置 (opens new window)
题解

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==NULL) return 0;
        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right);

        int midValue = 0;

        if(root->left && !root->left->left &&!root->left->right){
            midValue = root->left->val;
        }
        int sum = midValue + leftValue+rightValue;

        return sum;
    }
};

关键点
- 采用了后续遍历
- 迭代函数的返回值参与运算，存在这两层迭代：返回值的深入与回溯，方法的深入与回溯
- 返回值的深入与回溯，还涉及到计算，比常规的迭代函数复杂
- 涉及到左右叶子,需要与上层的逻辑关系判断的，则需要从根节点的角度出发

# 找出树最左下角的值

问题描述: 给定二叉树的根节点,找出最底层,最左边的值
力扣位置 (opens new window)
题解

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

关键点
- 涉及到层次,使用层序遍历
- 最左下方的节点，实质上就是层序遍历时，队列的最后一个元素节点的值

# 路径总和

问题描述: 给定一个二叉树和目标和，判断是否存在根节点到叶子节点路径之和为目标和。
力扣位置 (opens new window)
题解

class Solution {
private:
    bool traversal(TreeNode* cur,int count){
        if(!cur->left && !cur->right&&count==0) return true;
        if(!cur->left && !cur->right) return false;

        if(cur->left){
            count -=cur->left->val;
            if(traversal(cur->left,count)) return true;
            count +=cur->left->val;
        }

        if(cur->right){
            count-=cur->right->val;
            if(traversal(cur->right,count)) return true;
            count += cur->right->val;
        }
        return false;
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==NULL) return false;
        return traversal(root,targetSum-root->val);
    }
};

关键点
- 本质上使用了先序遍历;
- 先序遍历，可以控制遍历深度

# 中序与后续列表构建二叉树

问题描述: 给定一棵树的中序遍历和后续遍历序列，求该二叉树
力扣位置 (opens new window)
题解

class Solution {
private:
    TreeNode* traversal(vector<int>& inorder,vector<int>& postorder){
        if(postorder.size()==0) return NULL;

        int rootValue = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootValue);

        if(postorder.size()==1) return root;

        int delimiterIndex;
        for(delimiterIndex =0;delimiterIndex<inorder.size();delimiterIndex++){
            if(inorder[delimiterIndex] == rootValue) break;
        }

        vector<int> leftInorder(inorder.begin(),inorder.begin()+delimiterIndex);
        vector<int> rightInorder(inorder.begin()+delimiterIndex +1,inorder.end());

        postorder.resize(postorder.size()-1);

        vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
        vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());

        root->left = traversal(leftInorder,leftPostorder);
        root->right = traversal(rightInorder,rightPostorder);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() ==0 || postorder.size()==0) return NULL;

        return traversal(inorder,postorder);
    }
};

关键点
- 本质上使用了先序遍历
- 每次迭代，只为了找到根节点
- 迭代需要与数组分段结合使用

# 最二叉树的构建

问题描述: 给定一个列表，其满足最大二叉树的特性（根最大）， 求二叉树以及根
力扣位置 (opens new window)
题解

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {
            node->val = nums[0];
            return node;
        }
        // 找到数组中最大的值和对应的下标
        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;
        // 最大值所在的下标左区间 构造左子树
        if (maxValueIndex > 0) {
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        // 最大值所在的下标右区间 构造右子树
        if (maxValueIndex < (nums.size() - 1)) {
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }    
};

关键点
- 确定临界值，递归演化

# 二叉树的合并

问题描述：两颗二叉树合并成一颗新的树,新树的各节点值是原来各树节点值之和
力扣位置 (opens new window)
题解

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点，不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

关键点
- 两棵树的并行遍历
- 回溯法构件树

# 二叉搜索树的搜索

问题描述：从二叉搜索树中，找出以某个值的为根的子树；
力扣位置 (opens new window)
题解

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

关键点
- 处理递归返回值与回溯的关系;

# 二叉搜索树的验证

问题描述：判定给定的二叉树是否是合法的二叉搜索树
力扣位置 (opens new window)
题解

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

关键点
- 不能以左节点小于根，根小于右节点的思路来判定！，直观上很容易这样判定
- 等价于中序遍历结果为递增数列

# 二叉搜索树的最小绝对值差

问题描述：求非负二叉树任意两节点的最小绝对值差
力扣位置 (opens new window)
题解

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};

关键点
- 二叉搜索树等价于有序数组
- 求最值的常规处理方式

← 线型结构算法开发遇到过的坑 →