每日算法(一)——二叉树

判断二叉树是否为平衡二叉树

平衡二叉树

一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过1。

思路: 利用递归收集左右子树的深度以及子树是否是平衡二叉树实现函数返回一个ReturnData类

class ReturnData{
  // 是否平衡
        boolean bal;
  // 深度
        int deep;
        public ReturnData(boolean bal,int deep){
            this.bal = bal;
            this.deep = deep;
        }
    }

  public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return isB(root).bal;
        
    }
    public ReturnData isB(TreeNode root){
        if(root == null)return new ReturnData(true,0);
        ReturnData left = isB(root.left);
        ReturnData right = isB(root.right);
        int deeps = Math.max(left.deep,right.deep) + 1;
      // 如果高度差大于1 或者 左/右子树不平衡
        if(Math.abs(left.deep - right.deep) > 1 || !left.bal ||!right.bal)               return new ReturnData(false,deeps);
        else return new ReturnData(true,deeps);
        
    }

二叉树中找到一个节点的后继节点

有父节点

思路: > 根据中序遍历是升序可知后继为例: 1. 有右节点,则后继节点就是该右子树的最左节点 2. 没有右子树,则不断往上回溯找到 par.left = ch

    public TreeNode successor(TreeNode node){
        if( node == null){
            return null;
        }
        // 情况1,有右子树,则后继节点就是该右子树的最左节点
        if( node.right != null){
            TreeNode tmp = node.right;
            while(tmp.left != null)
                tmp = tmp.left;
            return tmp;
        }else{
            // 情况2 没有右子树,则不断往上回溯找到 par.left = ch
            TreeNode par = node.parent;
            TreeNode ch = node;
            while(par != null && ch == par.right){
                ch = par;
                par = par.parent;
            }
            return par;
        }

    }

    public TreeNode predecessor(TreeNode node){
        // 和后继是反过来的
        if( node == null){
            return null;
        }
        // 情况1,有左子树,则后继节点就是该左子树的最右节点
        if( node.left!= null){
            TreeNode tmp = node.left;
            while(tmp.right != null)
                tmp = tmp.right;
            return tmp;
        }else{
            // 情况2 没有左子树,则不断往上回溯找到 par.right = ch
            TreeNode par = node.parent;
            TreeNode ch = node;
            while(par != null && ch == par.left){
                ch = par;
                par = par.parent;
            }
            return par;
        }
    }

无父节点

思路: 1. 情况1 p是最大节点没有后继返回null 2. 情况2 p有右子树找右子树最左节点 3. 情况3 p没有右子树快慢指针


    public TreeNode successor(TreeNode root, TreeNode node) {
        // 边界判断
        if (node == null) return null;
        // 情况1 p是最大节点 没有后继 返回null
        if (getMaxNode(node) == node) return null;
        // 情况2 p有右子树 找右子树最左节点
        if (node.right != null) return getMinNode(node.right);
        // 情况3 p没有右子树
        TreeNode parent = root;
        TreeNode temp = root;
        while (parent != null) {
            if (parent == node) {
                break;
            } else if (node.val < parent.val) {
                temp = parent;
                parent = parent.left;
            } else {
                parent = parent.right;
            }
        }
        return temp;
    }

    public TreeNode getMaxNode(TreeNode node) {
        if (node == null) return null;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public TreeNode getMinNode(TreeNode node) {
        if (node == null) return null;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

二叉树找到两个节点的最近公共祖先

思路: 利用递归看是否能够找到两个节点找到后就返回如果左子树和右子树找到的节点都不为空说明左/右子树都发现了2个节点中的一个则2者节点往上走首先在遍历到的当前节点相遇如果有一个为空一个不为空说明可能当前的node 是2者的最近公共祖先或者是二者中的一个

 public static Node findFather(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = findFather(head.left, o1, o2);
        Node right = findFather(head.right, o1, o2);
        if (left != null && right != null) return head;
        return left != null ? left : right;
    }

二叉树结点间的最大距离

思路: 最大距离来自于

左/右子树的最大距离
经过当前节点的最远距离

于是用一个全局变量保存左/右子树据结点的最大距离

   public static int maxDistance(Node head) {
        int[] record = new int[1];
        return posOrder(head, record);
    }

    private static int posOrder(Node head, int[] record) {
        if (head == null) {
            record[0] = 0;
            return 0;
        }

        int lMax = posOrder(head.left, record);
      // 距离左子节点的最大距离
        int maxfromLeft = record[0];
        int rMax = posOrder(head.right, record);
       // 距离右子节点的最大距离
        int maxfromRight = record[0];
        int curNodeMax = maxfromLeft + maxfromRight + 1;
        record[0] = Math.max(maxfromLeft, maxfromRight) + 1;
        return Math.max(Math.max(lMax, rMax), curNodeMax);
    }

每日算法(一) 二叉树

目录