高频面试算法题--二叉树

1.二叉树的前序、中序、后序的非递归遍历
2.返回一个二叉树中某节点的后继节点(leetcode510)
后继节点的含义为一颗二叉树中序遍历的某节点的下一个节点，前驱节点为上一个节点。

解法：（1）从parent节点一直找到根节点，然后中序遍历该二叉树（时间复杂度较大）
（2）从二叉树的中序遍历来看：一个节点A如果有右子树，则A的后继节点一定是该右子树的最左节点；

如果A没有右子树，则通过parent指针往上找。一直到本节点是其父节点的左子树，则这个父节点就是A的后继节点。(同理可以得到前驱节点)



3.二叉树的序列化与反序列化（leetcode297）
一个二叉树的先序序列化

public class Codec {
//思路：递归
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return "#_";
        String res = root.val + "_";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split("_");
        Queue<String> queue = new LinkedList<String>();
        for(int i = 0; i < values.length; i++)
            queue.offer(values[i]);
        return reconPreOrder(queue);
    }
    public TreeNode reconPreOrder(Queue<String> queue)
    {
        String value = queue.poll();
        if(value.equals("#"))
            return null;
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = reconPreOrder(queue);
        head.right = reconPreOrder(queue);
        return head;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

4.求一颗完全二叉树的节点个数
要求时间复杂度小于 O(N)
1 << (h - level)表示2的(h - level)次方。
时间复杂度O(log^2N)，比O(N)低很多。二叉树每一次仅遍历一个节点复杂度O(logN)，每个节点找边界复杂度O(logN)