第5章 第5节 树

推荐给朋友

● 问题:手撕代码,根据前序,中序创建二叉树。

参考回答:

public class Solution {
public TreeNode func(int [] pre, int s1, int e1, int [] in, int s2, int e2) {
if(s1>e1||s2>e2) return null;
TreeNode p = new TreeNode(pre[s1]);
for(int i=s2;i<=e2;i++){
if(pre[s1]==in[i]){
p.left = func(pre,s1+1,s1+i-s2,in,s2,i-1);
p.right = func(pre,s1+i-s2+1,e1,in,i+1,e2);
}
}
return p;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return func(pre,0,pre.length-1,in,0,in.length-1);
}
}

解析:剑指OFFER原题:构建二叉树。通过前序第一个节点(根节点)分割后序遍历的字符串。分别递归的根节点的左右节点。

● 算法题:从右边看被遮挡的二叉树,求露出的node

参考回答:

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;


//树节点类

class TreeElement {
int val;
TreeElement left;
TreeElement right;
TreeElement(int x) {
val = x;
}
}
public class RightSideView {
public List<Integer> rightSideView(TreeElement root) {
List<Integer> result = new LinkedList<>();
if(root != null) {
Deque<TreeElement> deque = new LinkedList<>();

//当前层的节点数

int current = 1;

//下一层的节点数

int next = 0;
TreeElement node;
deque.addLast(root);
while(deque.size() > 0) {

//取第一个节点

node = deque.removeFirst();
current--;

//添加非空的节点

if(node.left != null) {
next++;
deque.addLast(node.left);
}

//添加非空的节点

if(node.right != null) {
next++;
deque.addLast(node.right);
}

//如果当前层已经处理完了

if(current == 0) {

//保存此层的最右一个节点值

result.add(node.val);

//设置下一层的元素个数

current = next;
next = 0;
}
}
}
return result;
}
}

● 算法题,给前序和中序,求出二叉树

参考回答:

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class TestRecoverBinaryTree {
public TreeNode reConstructBinaryTree(int [] preOrder,int [] inOrder)
{
int pLen = preOrder.length;
int iLen = inOrder.length;
if(pLen==0 && iLen==0)
{
return null;
}
return  btConstruct( preOrder, inOrder, 0, pLen-1,0, iLen-1);
}

//构建方法,pStart和pEnd分别是前序遍历序列数组的第一个元素和最后一个元素;

//iStart和iEnd分别是中序遍历序列数组的第一个元素和最后一个元素。

public TreeNode btConstruct(int[] preOrder, int[] inOrder, int pStart, int pEnd,int iStart,int iEnd)

{

//建立根节点

TreeNode tree = new TreeNode(preOrder[pStart]);
tree.left = null;
tree.right = null;
if(pStart == pEnd && iStart == iEnd)
{
return tree;
}
int root = 0;

//找中序遍历中的根节点

for(root=iStart; root<iEnd; root++)
{
if(preOrder[pStart] == inOrder[root])
{
break;
}
}

//划分左右子树

int leftLength = root - iStart;//左子树

int rightLength = iEnd - root;//右子树

//遍历左子树

if(leftLength>0)
{
tree.left = btConstruct(preOrder, inOrder,  pStart+1,  pStart+leftLength, iStart, root-1);
}

//遍历右子树

if(rightLength>0)
{
tree.right = btConstruct(preOrder, inOrder,  pStart+leftLength+1,  pEnd, root+1, iEnd);
}
return tree;
}
}

● 算法题,trim二叉搜索树

参考回答:

class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if(root==NULL)
return NULL;
if(root->val<L)
return trimBST(root->right,L,R);
else if(root->val>R)
return trimBST(root->left,L,R);
else
{
root->left=trimBST(root->left,L,R);
root->right=trimBST(root->right,L,R);
}
return root;
}
};

● 红黑树

参考回答:

红黑树(Red Black Tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

它的统计性能要好于平衡二叉树,因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。其他平衡树还有:AVL,SBT,伸展树,TREAP等等。

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点(NIL节点,空节点)是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

在很多树数据结构的表示中,一个节点有可能只有一个子节点,而叶子节点不包含数据。用这种范例表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,本文中我们使用"nil 叶子" 或"空(null)叶子",如上图所示,它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略,导致了这些树好象同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有节点都有两个子节点,尽管其中的一个或两个可能是空叶子。