目录

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

先序中序后序两两结合组成树

给定一个二叉树正确的先序,中序,后序数组 重构出原来的二叉树 并返回头节点

思路: 根据 3种遍历方式的特点 先序遍历的第一个元素为树的根节点 后序遍历的最后一个元素为树的根节点 利用递归方式重构树

 public Node buildTree(int[] preorder, int[] inorder) {
        return buildTrees(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private Node buildTrees(int[] preorder, int pleft, int pright, int[] inorder, int inleft, int inright) {
        if(pleft > pright || inleft > inright) return null;
      // 头节点
        Node root = new Node(preorder[pleft]);
        int rootIn = inleft;
        while(preorder[pleft] != inorder[rootIn]){
            rootIn++;
        }
      // 左子树的长度
        int left = rootIn - inleft;
      // 先序/中序遍历的左子树范围
        root.left = buildTrees(preorder,pleft +1,pleft + left,inorder,inleft,rootIn - 1);
      // 先序/中序遍历的右子树范围
        root.right = buildTrees(preorder,pleft + left + 1,pright,inorder,rootIn + 1,inright);
        return root;
    }

 public Node buildTree(int[] inorder, int[] postorder) {
        return buildTrees(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private Node buildTrees(int[] inorder, int inLeft, int inRight, int[] postorder, int posLeft, int posRight) {
        if (inLeft > inRight || posLeft > posRight) return null;
      // 头节点
        Node root = new Node(postorder[posRight]);
        int rootIn = inLeft;
        while(inorder[rootIn] != postorder[posRight]){
            rootIn++;
        }
        int leftLen = rootIn - inLeft;
        root.left = buildTrees(inorder,inLeft,rootIn - 1,postorder,posLeft,posLeft + leftLen - 1);
        root.right= buildTrees(inorder,rootIn + 1,inRight,postorder,posLeft + leftLen,posRight - 1);
        return root;
    }

特别注意: 先序和后序的组合并不一定能重构出正确的树

​ A A 二者的先序和后序 都是 AB BA

​ /

B B

即 只有每个结点的孩子树为 0 或 2 的二叉树才能被先序和后序正确还原

public static Node prePosToTree(int[] pre, int[] pos) {
		if (pre == null || pos == null) {
			return null;
		}
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < pos.length; i++) {
			map.put(pos[i], i);
		}
		return prePos(pre, 0, pre.length - 1, pos, 0, pos.length - 1, map);
	}

	public static Node prePos(int[] p, int pi, int pj, int[] s, int si, int sj,
			HashMap<Integer, Integer> map) {
		Node head = new Node(s[sj--]);
		if (pi == pj) {
			return head;
		}
		int index = map.get(p[++pi]);
		head.left = prePos(p, pi, pi + index - si, s, si, index, map);
		head.right = prePos(p, pi + index - si + 1, pj, s, index + 1, sj, map);
		return head;
	}

通过先序和中序生成后序数组

public static int[] getPosArray(int[] pre, int[] in) {
		if (pre == null || in == null) {
			return null;
		}
		int len = pre.length;
		int[] pos = new int[len];
  // 预先保存中序遍历时每个结点的位置 不必像上一题中遍历求解位置
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < len; i++) {
			map.put(in[i], i);
		}
		setPos(pre, 0, len - 1, in, 0, len - 1, pos, len - 1, map);
		return pos;
	}

	public static int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj,
			int[] s, int si, HashMap<Integer, Integer> map) {
		if (pi > pj) {
			return si;
		}
      // 填充数组
		s[si--] = p[pi];
		int i = map.get(p[pi]);
		si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map);
		return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map);
	}

统计完全二叉树的节点数

满二叉树引出: 满二叉树:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点

完全二叉树: 有左无右 至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上

思路: 如果右子树没有到达最后一层 则说明右子树为满二叉树 否则左子树为满二叉树

一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;

　　它的叶子数是： 2^h

　　第k层的结点数是： 2^(k-1)

　　总结点数是： 2^k-1 (2的k次方减一)

public static int nodeNum(Node head) {
		if (head == null) {
			return 0;
		}
		return bs(head, 1, mostLeftLevel(head, 1));
	}
// bs(node,l,h) 以node为头的完全二叉树的节点数是多少
	public static int bs(Node node, int l, int h) {
		if (l == h) {
			return 1;
		}
		if (mostLeftLevel(node.right, l + 1) == h) {
			return (1 << (h - l)) + bs(node.right, l + 1, h);
		} else {
			return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
		}
	}

	public static int mostLeftLevel(Node node, int level) {
		while (node != null) {
			level++;
			node = node.left;
		}
		return level - 1;
	}