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)
京公网安备 11010502036488号