二叉树

2019/10/09 Algorithm

二叉树是数据结构中最重要的树形结构,本文主要描述关于二叉树的一些基本操作以及算法分析。

普通二叉树

判断两棵树是否相等

/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL){
            return true;
        } else if (p != NULL && q != NULL && p->val == q->val) {
            if(isSameTree(p->left, q->left) && isSameTree(p->right, q->right)){
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
};

判断一棵树是否对称

/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL){
            return true;
        } else if (p != NULL && q != NULL && p->val == q->val) {
            if(isSameTree(p->left, q->left) && isSameTree(p->right, q->right)){
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    void reverse(TreeNode* T, TreeNode* root){
        if(root == NULL)
            return;
        T->val = root->val;
        if(root->right != NULL)
            T->left = new TreeNode(root->right->val);
        else
            T->left = NULL;
        if(root->left != NULL)
            T->right = new TreeNode(root->left->val);
        else
            T->right = NULL;
        reverse(T->right, root->left);
        reverse(T->left, root->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        TreeNode* T = new TreeNode(0);
        reverse(T, root);
        return isSameTree(T, root);
    }
};

找出二叉树的最大深度

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

找出二叉树的最小深度

/**
 * 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 minDepth(TreeNode* root) {
        if(root == NULL){
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        int res = 1;
        while(!q.empty()){
            int len = q.size();
            for(int i=0; i<len; i++){
                if(q.front()->left != NULL){
                    q.push(q.front()->left);
                }
                if(q.front()->right != NULL){
                    q.push(q.front()->right);
                }
                if(q.front()->left == NULL && q.front()->right == NULL){
                    return res;
                }
                q.pop();
            }
            res++;
        }
        return 0;
    }
};

找出二叉树自底向上的层次遍历

/**
 * 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>> vec;
        if(root == NULL){
            return vec;
        }
        queue<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            int len = s.size();
            vector<int> t;
            for(int i=0; i<len; i++){
                t.push_back(s.front()->val);
                if(s.front()->left != NULL){
                    s.push(s.front()->left);
                }
                if(s.front()->right != NULL){
                    s.push(s.front()->right);
                }
                s.pop();
            }
            vec.insert(vec.begin(), t);
        }
        return vec;
    }
};

高度平衡二叉树

高度平衡二叉树是指二叉树每个节点的左右两个子树的高度差的绝对值不超过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:
    bool isBalanced(TreeNode* root) {
        if(root == NULL)
            return true;
        return isBalanced(root->left) && isBalanced(root->right) && abs(getDeep(root->left) - getDeep(root->right)) < 2;
    }
    
    int getDeep(TreeNode* root){
        if(root == NULL)
            return 0;
        int left = getDeep(root->left);
        int right = getDeep(root->right);
        return left > right ? left + 1 : right + 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:
    vector<string> res;
    vector<int> ans;
    void array2string(){
        string path = "";
        for(int i=0; i<ans.size()-1; i++){
            path += to_string(ans[i]) + "->";
        }
        path += to_string(ans[ans.size()-1]);
        res.push_back(path);
    }
    void walk(TreeNode* root){
        if(root == NULL){
            return;
        }
        ans.push_back(root->val);
        walk(root->left);
        walk(root->right);
        if(root->left == NULL && root->right == NULL){
            array2string();
        }
        ans.pop_back();
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        walk(root);
        return res;
    }
};

二叉树的路径之和 I

这里的二叉树路径是指从根节点出发到叶子节点为止,给定target值,判断二叉树是否存在路径,其路径之和等于target。

/**
 * 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 hasPathSum(TreeNode* root, int sum) {
        if(root == NULL){
            return false;
        }
        if(root->left == NULL && root->right == NULL && root->val == sum){
            return true;
        } else if(hasPathSum(root->left, sum-root->val)) {
            return true;            
        } else if(hasPathSum(root->right, sum-root->val)) {
            return true;
        } else {
            return false;
        }
    
    }
};

二叉树的路径之和 II

这里的二叉树路径是指从任意节点出发,自上往下的路径。给定target值,找出所有等于target值的路径总数。

/**
 * 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 pathSum(TreeNode* root, int sum) {
        if(root == NULL){
            return 0;
        }
        return t(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        }
private:
    int t(TreeNode* root, int sum){
        if(root == NULL){
            return 0;
        }
        int res = 0;
        if(root->val == sum){
            res++;
        }
        return res + t(root->left, sum-root->val) + t(root->right, sum-root->val);
    }
};

翻转二叉树

将二叉树按中心轴对称翻转。据说Homebrew的作者Max Howell在面试谷歌的时候不会写这道题目。

/**
 * 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* invertTree(TreeNode* root) {
        if(root == NULL){
            return root;
        }
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* t = root->left;
        root->left = root->right;
        root->right = t;
        return root;
    }
};

二叉树的直径

一颗二叉树的直径长度是任意两个节点路径长度(节点间的边的数目)中的最大值,路径可能穿过root节点。

/**
 * 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 temp = 0;
    int treeHight(TreeNode* root){
        if(root == NULL){
            return 0;
        }
        int L = treeHight(root->left);
        int R = treeHight(root->right);
        temp = max(R+L, temp);
        return max(R,L) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        treeHight(root);
        return temp;
    }
};

二叉树的坡度

一个节点的坡度是该节点的左子树节点之和与右子树节点之和的差的绝对值,空节点的坡度是0。二叉树的坡度是其所有节点的坡度之和。

/**
 * 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 temp;
    int TreeTilt(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }
        int L = TreeTilt(root->left);
        int R = TreeTilt(root->right);
        temp += abs(L-R);
        return L + R + root->val;
    }
    int findTilt(TreeNode* root) {
        TreeTilt(root);
        return temp;
    }
};

相同的二叉树子树

给定两棵二叉树,判断它们是否具有相同的子树。

/**
 * 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 w = 0;
    void treeWalk(TreeNode* root, string& ans){
        if(root == NULL){
            if(w == 0)
                ans = ans + "L";
            if(w == 1)
                ans = ans + "R";
            return;
        }
        ans = ans + "#" + to_string(root->val);
        w = 0;
        treeWalk(root->left, ans);
        w = 1;
        treeWalk(root->right, ans);
        
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        string a, b;
        treeWalk(s, a);
        treeWalk(t, b);
        if(a.find(b) != a.npos){
            return true;
        } else {
            return false;
        }
    }
};

合并两棵二叉树

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

/**
 * 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:
    void walk(TreeNode* t1, TreeNode* t2, TreeNode* F1, TreeNode* F2){
        if(t1 != NULL && t2 != NULL){
            t1->val += t2->val;
        }
        if(t1 == NULL && t2 != NULL){
            if(t2 == F2->left)
                F1->left = t2;
            if(t2 == F2->right)
                F1->right = t2;
            return;
        }
        if(t1 != NULL && t2 == NULL){
            return;
        }
        if(t1 == NULL && t2 == NULL){
            return;
        }
        walk(t1->left, t2->left, t1, t2);
        walk(t1->right, t2->right, t1, t2);
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == NULL){
            walk(t2, t1, NULL, NULL);
            return t2;
        } else {
            walk(t1, t2, NULL, NULL);
            return t1;
        }
    }
};

计算二叉树的层平均值

/**
 * 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<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> L;
        queue<TreeNode*> R;
        vector<double> ans;
        L.push(root);
        while(!L.empty()){
            double temp = 0;
            int len = L.size();
            while(!L.empty()){
                TreeNode* t = L.front();
                if(t->left != NULL)
                    R.push(t->left);
                if(t->right != NULL)
                    R.push(t->right);
                temp += t->val;
                L.pop();
            }
            ans.push_back(double(temp/len));
            // 到此L为空,R存储了下一层。
            L.swap(R);
        }
        return ans;
    }
};

二叉树最长同值路径

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。(两个节点之间的路径长度由它们之间的边数表示)

/**
 * 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 ans;
    int walk(TreeNode* root){
        if(root == NULL)
            return 0;
        int L = walk(root->left);
        int R = walk(root->right);
        int LL = 0, RR = 0;
        if(root->left != NULL && root->val == root->left->val)
            LL += L + 1;
        if(root->right != NULL && root->val == root->right->val)
            RR += R + 1;
        ans = max(ans, LL+RR);
        return max(LL, RR);
    }
    int longestUnivaluePath(TreeNode* root) {
        ans = 0;
        walk(root);
        return ans;
    }
};

二叉搜索树

将升序的数列转化为二叉搜索树

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0)
            return NULL;
        return array2BST(nums, 0, nums.size()-1);
    }
    
    TreeNode* array2BST(vector<int>& nums, int i, int j){
        if(i == j){
            return new TreeNode(nums[i]);
        }
        int mid = i + (j-i)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        if(mid != i)
            root->left = array2BST(nums, i, mid-1);
        root->right = array2BST(nums, mid+1, j);
        return root;
    }
};

二叉搜索树的最近公共祖先

给定二叉搜索树,找出该树中两个指定节点的最近公共祖先。最近公共祖先的定义是,对于有根树T的两个节点p、q,最近公共祖先是一个满足p、q的祖先并且深度尽可能大的节点。最近公共祖先节点可以是节点本身。

/**
 * 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;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL){
            return root;
        } else if (left != NULL) {
            return left;
        } else if (right != NULL) {
            return right;
        }
        return NULL;
    }
};

二叉搜索树中的众数

给定一个具有相同值的二叉搜索树,找出其中的所有众数。

/**
 * 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 cur;
    vector<int> res;
    int maxcnt = 0;
    int cnt = 0;
    void walk(TreeNode* root){
        if(root == NULL){
            return;
        }
        walk(root->left);
        if(root->val == cur){
            cnt++;
        } else {
            if(cnt > maxcnt){
                res.clear();
                res.push_back(cur);
                maxcnt = cnt;
            } else if (cnt == maxcnt){
                res.push_back(cur);
            }
            cnt = 1;
            cur = root->val;
        }
        walk(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        if(root == NULL){
            return res;
        }
        TreeNode* t = root;
        while(t->left != NULL){
            t = t->left;
        }
        cur = t->val;
        walk(root);
        if(cnt > maxcnt){
            res.clear();
            res.push_back(cur);
            maxcnt = cnt;
        } else if (cnt == maxcnt){
            res.push_back(cur);
        }
        return res;
    }
};

二叉搜索树中的最小绝对差

给定一个所有节点都是非负值的二叉搜索树,求树中任意两个节点的差的绝对值的最小值。

/**
 * 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:
    void fun(TreeNode* root, vector<int>& path){
        if(root != NULL){
            fun(root->left, path);
            path.push_back(root->val);
            fun(root->right, path);
        }
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> ans;
        fun(root, ans);
        int res = 1000000;
        for(int i=0; i<ans.size()-1; i++){
            if(ans[i+1] - ans[i] < res){
                res = ans[i+1] - ans[i];
            }
        }
        return res;
    }
};

将二叉搜索树转换为累加树

累加树(Greater Tree)是指在原本二叉树的基础上,每个节点的值更新为原来的值加上所有大于它的节点值之和。

/**
 * 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 temp = 0;
    void fun(TreeNode* root){
        if(root != NULL){
            fun(root->right);
            root->val += temp;
            temp = root->val;
            fun(root->left);
        }
    }
    TreeNode* convertBST(TreeNode* root) {
        fun(root);
        return root;
    }
};

二叉搜索树的两数之和

给定一个二叉搜索树和target值,判断树中是否存在两数之和等于target。

/**
 * 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 Search(TreeNode* root, int t){
        if(root == NULL){
            return false;
        }
        if(t == root->val){
            return true;
        } else if (t > root->val){
            return Search(root->right, t);
        } else {
            return Search(root->left, t);
        }
    }
    void Walk(TreeNode* root, vector<int>& ans){
        if(root == NULL){
            return;
        }
        ans.push_back(root->val);
        Walk(root->left, ans);
        Walk(root->right, ans);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> res;
        Walk(root, res);
        for(int i=0; i<res.size(); i++){
            // 二叉搜索树中不存在相同的元素。
            // 因此k-res[i] != res[i]。
            if(k!=2*res[i] && Search(root, k-res[i])){
                return true;
            }
        }
        return false;
    }
};

修剪二叉搜索树

给定一个二叉搜索树,以及区间[L, R]。通过修剪二叉搜索树使得所有的节点的值都在区间[L, R]内。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 朴素的思想是,将二叉搜索树转为线性结构,然后搜索LR区间的值,再从线性结构构建二叉搜索树。参见108题,这样的朴素的作法是错误的。

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

二叉搜索树的搜索

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

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

二叉搜索树的节点最小差值

找出二叉搜索树中任意两个节点之间的差的最小值。

/**
 * 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:
    void walk(TreeNode* root, vector<int>& ans){
        if(root == NULL){
            return;
        }
        walk(root->left, ans);
        ans.push_back(root->val);
        walk(root->right, ans);
    }
    int minDiffInBST(TreeNode* root) {
        vector<int> a;
        walk(root, a);
        int res = 10000;
        for(int i=0; i<a.size()-1; i++){
            // cout << a[i] << " " << endl;
            res = min(a[i+1] - a[i], res);
        }
        return res;
    }
};

Search

    Table of Contents