树的相关算法

作者: 飞白非白 | 来源:发表于2018-12-04 23:24 被阅读2次
  • 二叉树的最近公共祖先
// 给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先
// 思路:从根节点开始遍历,如果node1和node2中的任一个和root匹配,那么root就
// 是最低公共祖先。 如果都不匹配,则分别递归左、右子树,如果有一个 
// 节点出现在左子树,并且另一个节点出现在右子树,则root就是最低公共祖先.  
// 如果两个节点都出现在左子树,则说明最低公共祖先在左子树中,否则在右子树。

public class Solution {  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        //发现目标节点则通过返回值标记该子树发现了某个目标结点  
        if(root == null || root == p || root == q) return root;  
        //查看左子树中是否有目标结点,没有为null  
        TreeNode left = lowestCommonAncestor(root.left, p, q);  
        //查看右子树是否有目标节点,没有为null  
        TreeNode right = lowestCommonAncestor(root.right, p, q);  
        //都不为空,说明做右子树都有目标结点,则公共祖先就是本身  
        if(left!=null&&right!=null) return root;  
        //如果发现了目标节点,则继续向上标记为该目标节点  
        return left == null ? right : left;  
    }  
}
  • 顺序结构的二叉树的公共祖先
void k(int i,int j)
{
    while(true)
    {
        if(i==j)
        {
            break;
        }
        if(i>j)
        {
            i/=2;
        }
        else
        {
            j/=2;
        }
 
    }
    printf("%d\n",i);
}

  • 二叉树的所有路径
/**
 * 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> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root==nullptr)
            return res;
        string temp;
        binary(root, temp, res);
        return res;
        
    }
    void binary(TreeNode* root, string temp, vector<string> &res )
    {
        if(!root->left && !root->right)
            res.push_back(temp+to_string(root->val));
        if(root->left)
        {
            binary(root->left, temp+to_string(root->val)+"->",res);
        }
        if(root->right)
        {
            binary(root->right, temp+to_string(root->val)+"->",res);
        }
    }
};
  • 翻转一棵二叉树||交换左右子树
// 如果一个节点是叶子节点,则不做操作;如果一个节点只有左孩子或者右孩子,则
// 进行交换,原来的孩子为空;如果一个节点既有左孩子和右孩子,则交换左右孩子

// 交换左右子树
void ReverseLeftRightChild(BiTNode **T)
{
    // 如果是叶子节点,则递归结束
    if (*T == NULL)
    {
        return;
    }
 
    swap((*T)->lChild, (*T)->rChild); // 直接使用swap交换函数比较方便,直接交换指针;
    ReverseLeftRightChild(&((*T)->lChild));
    ReverseLeftRightChild(&((*T)->rChild));
}


  • 给定一个二叉树,找出其最小深度
/**
 * Definition for binary tree
 * 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;
        if (root->left == NULL && root->right == NULL) return 1;
        
        if (root->left == NULL) return minDepth(root->right) + 1;
        else if (root->right == NULL) return minDepth(root->left) + 1;
        else return 1 + min(minDepth(root->left), minDepth(root->right));
    }
    
};
  • 给定一个二叉树,找出其最大深度
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxDepth(TreeNode *root) {
       if(root==NULL){
           return NULL;
       }
       int left=maxDepth(root->left);
       int right=maxDepth(root->right);
       return (left>right)?(left+1):(right+1);
    }
};


  • 求树的宽度
// 使用队列,层次遍历二叉树。在上一层遍历完成后,下一层的所有节点已经放到队
// 列中,此时队列中的元素个数就是下一层的宽度。以此类推,依次遍历下一层即可
// 求出二叉树的最大宽度

    public static int getMaxWidth(TreeNode root) {
        if (root == null)
            return 0;

        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        int maxWitdth = 1; // 最大宽度
        queue.add(root); // 入队

        while (true) {
            int len = queue.size(); // 当前层的节点个数
            if (len == 0)
                break;
            while (len > 0) {// 如果当前层,还有节点
                TreeNode t = queue.poll();
                len--;
                if (t.left != null)
                    queue.add(t.left); // 下一层节点入队
                if (t.right != null)
                    queue.add(t.right);// 下一层节点入队
            }
            maxWitdth = Math.max(maxWitdth, queue.size());
        }
        return maxWitdth;
    }
  • 判断平衡二叉树
// 左右子树的深度差的绝对值不大于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 judge(TreeNode* root,bool &ans)
    {
        if(root)
        {
            int ans1 = judge(root->left,ans);
            int ans2 = judge(root->right,ans);
            if(abs(ans1-ans2)>1) ans=false;
            return max(ans1,ans2)+1;
        }
        else return 0;
    }
    
    bool isBalanced(TreeNode* root) {
        bool ans = true;
        judge(root,ans);
        return ans;
    }
};
  • 查找二叉排序树中的第k小元素
1、计算左子树元素个数left。

2、 left+1 = K,则根节点即为第K个元素

      left >=k, 则第K个元素在左子树中,

     left +1 <k, 则转换为在右子树中,寻找第K-left-1元素。


   int calcTreeSize(TreeNode* root){  
        if (root == NULL)  
            return 0;  
        return 1+calcTreeSize(root->left) + calcTreeSize(root->right);          
    }  

      int kthSmallest(TreeNode* root, int k) {  
        if (root == NULL)  
            return 0;  
        int leftSize = calcTreeSize(root->left);  
        if (k == leftSize+1){  
            return root->val;  
        }else if (leftSize >= k){  
            return kthSmallest(root->left,k);  
        }else{  
            return kthSmallest(root->right, k-leftSize-1);  
        }  
    }  




  • 求二叉树中叶子节点个数
size_t _LeafSize(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        if (root->_letf == NULL &&root->_right == NULL)
        {
            return 1;
        }
        size_t i = _LeafSize(root->_letf);
        size_t j = _LeafSize(root->_right);
        return i + j;
    }

  • 二叉树中第K层节点个数
size_t _GetKLevel(Node* root, size_t k)
    {
        if (root == NULL)
        {
            return 0;
        }
        if (k == 1)
        {
            return 1;
        }

        // 此处递归的意义为:某个节点的第n层节点实际上是其孩子节点的第n-1层节点
        return _GetKLevel(root->_letf, k - 1) + _GetKLevel(root->_right, k - 1);
    }

相关文章

  • 树的相关算法

    二叉树的最近公共祖先 顺序结构的二叉树的公共祖先 二叉树的所有路径 翻转一棵二叉树||交换左右子树 给定一个二叉树...

  • 数据分析方法-决策树

    大家好,这篇文章我们探讨下,决策树算法的相关的知识,决策树是一种分类算法,现在也可以应用与回归,决策树算法的实现有...

  • AVL树的调整相关算法

    AVL树的左旋与右旋等操作 LL旋转: 导致失衡的是节点node的左子树的左孩子,称为LL 调整算法如下:对于节点...

  • 第一章(1.2) 机器学习算法工程师技能树

    一、机器学习算法工程师需要掌握的技能 机器学习算法工程师需要掌握的技能包括 (1)基础数据结构与算法 树与相关算法...

  • 二叉树遍历

    前言 在学习或工作中,总会遇到和算法相关的问题。而二叉树在算法中是绕不过的一个场景。 这里介绍下二叉树的相关遍历方...

  • 机器学习-决策树原理 Python

    由于最近项目的需要,学习了分类算法--决策树,从逐步了解决策树,然后到手动在Excel里面模拟计算相关算法,最后到...

  • LeetCode 二叉树专题 (1)二叉树知识 和 解题框架

    算法题中树相关的题目是相对比较难的,同时在开始刷算法题时,也最好先从树型题刷起,因为他的解题思想对以后各种题型都是...

  • OC二叉树相关操作

    二叉树-你必须要懂!(二叉树相关算法实现-iOS) http://www.cnblogs.com/manji/p/...

  • 图的相关算法(二):最小生成树算法

    最小生成树 在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到...

  • 3. 二叉搜索树 --- BST(Binary Search T

    BST : 二叉搜索树 树表结构查找相关算法 主要思想 : 循关键码访问 key 条件 : 关键码之间大小比较...

网友评论

    本文标题:树的相关算法

    本文链接:https://www.haomeiwen.com/subject/fcybcqtx.html