二叉树常见问题

发表于 | 更新于 | 字数统计2.2k字 | 阅读时长9分钟 | 分类于

链表相关问题

  1. 在O(1)时间删除链表节点
  2. 单链表的转置
  3. 求链表倒数第k个节点
  4. 求链表的中间节点
  5. 判断单链表是否存在环
  6. 找到环的入口点
  7. 编程判断两个链表是否相交
  8. 扩展：链表有环，如何判断相交
  9. 扩展：两链表相交的第一个公共节点

求二叉树的深度(从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为1。)

private static int getTreeHeight(TreeNode root) {
    if (root == null)
        return 0;
    // 左子树depth与右子树depth的较大值+1即为tree的depth
    int left = getTreeHeight(root.left);
    int right = getTreeHeight(root.right);

    return left>right ? left+1:right+1;
}

求二叉树的节点个数

求二叉树第K层的节点个数

private static int kLevelNodeNumber(TreeNode root, int k) {
    // 第k层节点数可以看做是左子树的k-1层节点数+右子树的k-1层节点数
    if (root == null || k <= 0)
        return 0;
    if (k == 1)
        return 1;
    int leftNodeNum = kLevelNodeNumber(root.left, k-1);
    int rightNodeNum = kLevelNodeNumber(root.right, k-1);

    return leftNodeNum+rightNodeNum;
}

求二叉树中叶子节点的个数

private static int leafNodeNumber(TreeNode root) {
    if (root == null)
        return 0;
    if (root.left == null && root.right == null)
        return 1;
    return leafNodeNumber(root.left) + leafNodeNumber(root.right);

}

反转二叉树(求二叉树镜像) —- 递归和循环解法

判断两棵二叉树是否结构相同

private static boolean EqualsOrNot(TreeNode node1, TreeNode node2) {
    // 如果两棵二叉树都为空，返回真;一真一假则返回false
    if (node1 == null && node2 == null) 
        return true;
    else if(node1==null || node2==null)
        return false;
    boolean left = EqualsOrNot(node1.left, node2.left);
    boolean right = EqualsOrNot(node1.right, node2.right);
    // 如果对应的左子树和右子树都为true则返回真
    return left && right;
}

判断一个二叉树是否是完全二叉树

完全二叉树：二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边
思路：任意的一个二叉树，都可以补成一个满二叉树。这样中间就会有很多空洞。在广度优先遍历的时候，如果是满二叉树，或者完全二叉树，这些空洞是在广度优先的遍历的末尾，当我们遍历到空洞的时候，整个二叉树就已经遍历完成了。而如果遍历到空洞还没有完成遍历则说明它是非完全二叉树

private static boolean isCompleteBT(TreeNode root) {

    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    // 进行广度优先遍历（层次遍历），并把NULL节点也放入队列
    TreeNode node;
    queue.offer(root);
    while((node=queue.poll()) != null) {
        queue.offer(node.left);
        queue.offer(node.right);
    }
    // 有未访问到的的非NULL节点，则树存在空洞，为非完全二叉树
    while(!queue.isEmpty()) {
        if (queue.poll() != null)
            return false;
    }
    return true;
}

判断二叉树是不是平衡二叉树

平衡二叉树它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

private static int getTreeHeight(TreeNode root) {
    if (root == null)
        return 0;
    // 左子树depth与右子树depth的较大值+1即为tree的depth
    int left = getTreeHeight(root.left);
    int right = getTreeHeight(root.right);

    return left>right ? left+1:right+1;
}

private static boolean isBalanceBT(TreeNode root) {
    if (root == null)
        return true;
    int leftHeight = getTreeHeight(root.left);
    int rightHeight = getTreeHeight(root.right);
    // 左右子树的高度之差应该<=1;而且左右子树都应该是平衡二叉树
    if (Math.abs(leftHeight-rightHeight) > 1)
        return false;
    else
        return isBalanceBT(root.left) && isBalanceBT(root.right);
}

优化解法: 只后序遍历二叉树一次，一边遍历一边比较左右子树的深度差

判断二叉树B是不是A的子结构

思路: 第一步在树A中找到和B的根节点的值一样的节点R，第二步再判断A中以R为根节点的子树是不是包含和树B一样的结构

private boolean isBsubTreeOfA(TreeNode rootA, TreeNode rootB) {
    boolean res = false;
    if (rootA != null && rootB != null) {
        if (rootA.val == rootB.val)
            res = EqualsTreeOrNot.EqualsOrNot(rootA, rootB);// 判断两棵树是否结构相同
        if (!res)
            res = isBsubTreeOfA(rootA.left, rootB);
        if (!res)
            res = isBsubTreeOfA(rootA.right, rootB);
    }
    return res;
}

求二叉树中两个节点的最低公共祖先节点

// 二叉查找树
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    else if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    else
        return root;
}
// 普通树二叉树
public static TreeNode lowestCommonAncestorBT(TreeNode root, TreeNode p, TreeNode q) {
    // 对二叉树做一个前序遍历，如果找到目标节点或者到了叶节点就return,对于return的结果进行判断
    // ，两者都!null说明root就是这两个节点的最近公共父节点;否则返回非空的那一个节点；回溯过程中到达最近公共父节点时会满足两者都!null
    if (root == null || root == p || root == q)
        return root;
    TreeNode leftNode = lowestCommonAncestorBT(root.left, p, q);
    TreeNode rightNode = lowestCommonAncestorBT(root.right, p, q);
    if (leftNode != null && rightNode != null) {
        return root;
    } else if (leftNode != null) {
        return leftNode;
    } else {
        return rightNode;
    }
}

求二叉树中两个节点之间的最大距离

private static int getTreeHeight(TreeNode root) {
    if (root == null)
        return 0;
    // 左子树depth与右子树depth的较大值+1即为tree的depth
    int left = getTreeHeight(root.left);
    int right = getTreeHeight(root.right);

    return left>right ? left+1:right+1;
}

private static int findMaxDistance(TreeNode root) {
    if (root == null)
        return 0;
    // 左右子树中的最大距离
    int leftMaxDis = findMaxDistance(root.left);
    int rightMaxDis = findMaxDistance(root.right);

    // 左右子树的最大Height
    int leftHeight = 0, rightHeight = 0;
    if (root.left != null)
        leftHeight = getTreeHeight(root.left);
    if (root.right != null)
        rightHeight = getTreeHeight(root.right);

    int max = leftMaxDis > rightMaxDis ? leftMaxDis : rightMaxDis;
    return max>(leftHeight+rightHeight) ? max:(leftHeight+rightHeight);
}

将二叉查找树变为有序的双向链表

思路:将tree看做左子树，根节点，右子树三个部分，然后利用中序遍历先对左子树转变为双向链表然后连接根节点；然后将右子树转变为双向链表，根节点连接到该双向链表；最后返回一个有序双向链表的头结点

private static TreeNode BST2List(TreeNode root) {
    TreeNode lastNodeOfList = null;
    lastNodeOfList = convert(root, lastNodeOfList);
    // 将lastNodeOfList从双向链表尾部移动到头部
    while (lastNodeOfList != null && lastNodeOfList.left != null) {
        lastNodeOfList = lastNodeOfList.left;
    }
    return lastNodeOfList;
}

private static TreeNode convert(TreeNode root, TreeNode lastNodeOfList) {
    if (root == null) {
        return root;
    }
    // 转变左子树为双向链表
    if (root.left != null)
        lastNodeOfList = convert(root.left, lastNodeOfList);
    // 修改双链表尾节点为当前节点
    if (lastNodeOfList != null) {
        root.left = lastNodeOfList;
        lastNodeOfList.right = root;
    }
    lastNodeOfList = root;
    // 转变右子树为双向链表
    if (root.right != null)
        lastNodeOfList = convert(root.right, lastNodeOfList);
    // 返回值为双链表尾节点
    return lastNodeOfList;
}

由前序遍历序列和中序遍历序列重建二叉树

二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。
递归解法：

  1. 如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。
  2. 创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍历序列，重建左右子树。

二叉树的下一个节点(给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点left和right，同时包含指向父结点的指针next)

思路: 三种情况

  1. 如果一个结点有右子树，那么它的下一个结点就是它的右子树中的左子结点。也就是说右子结点出发一直沿着指向左子结点的指针，我们就能找到它的下一个结点。

  2. 如果一个结点没有右子树，又可以分为两种情况：

    • 如果结点是它父节点的左子结点，那么它的下一个结点就是它的父结点。

    • 如果一个结点既没有右子树，并且它还是它父结点的右子结点。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父结点的左结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。

      public TreeLinkNode GetNext(TreeNode pNode) {
    TreeNode curNode = null;
    //第一步：判断是否有右孩子
    if(pNode.right != null){
        curNode = pNode.right;
        while(curNode.left != null) curNode = curNode.left;
        return curNode;
    }
    //第二步：判断是否是其父节点的左孩子
    if(pNode.next == null) return null;
    if(pNode == pNode.next.left){
        return pNode.next;
    }
    //第三步：向上找其父节点，直到父节点是其父节点的父节点的左孩子
    curNode = pNode.next;
    while(curNode.next != null){
        if(curNode == curNode.next.left){
            return curNode.next;
        }
        //继续向上找父节点
        curNode = curNode.next;
    }
    return null;
}