树的相关算法

• 二叉树的最近公共祖先

// 给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先
// 思路：从根节点开始遍历，如果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);
    }