『剣指offer第2版』面接問題36:二叉木と双方向チェーンテーブル(java)
1570 ワード
タイトルの説明
ツリーを入力し、ツリーをソートされた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
テーマ分析題の要求は順序付けの双方向チェーンテーブルであり、二叉探索木の中序遍歴は各ノードを小さいから大きいまで遍歴するので、中序遍歴と結合することが考えられる. ツリーは2つのサブノードを指すポインタであり、双方向チェーンテーブルも同様の構造であり、両者の構造は類似しており、ツリーのleftポインタをチェーンテーブルとして前のノードを指すポインタとし、ツリーrightポインタをチェーンテーブルとして後のノードを指すポインタとすることができる. ツリーのいずれかのノードについて、その前のノードは、その左のサブツリーがソートチェーンテーブルの最後のノードに変換され、その後のノードは、サブツリーからチェーンテーブルに変換された最初のノードである.再帰でできるのは明らかだ.
コード#コード#
ツリーを入力し、ツリーをソートされた双方向チェーンテーブルに変換します.新しいノードを作成できない必要があります.ツリー内のノードポインタの方向を調整するしかありません.
テーマ分析
コード#コード#
public TreeNode convert(TreeNode root){
if (root == null) {
return null;
}
// lastListNode
TreeNode lastListNode = rConvert(root, null);
TreeNode headListNode = lastListNode;
//
while (headListNode != null && headListNode.left != null) {
headListNode = headListNode.left;
}
return headListNode;
}
/**
* @param curNode
* @param lastListNode
* @return
*/
TreeNode rConvert(TreeNode curNode, TreeNode lastListNode){
if (curNode == null) {
return null;
}
if (curNode.left != null) {
lastListNode = rConvert(curNode.left, lastListNode);
}
curNode.left = lastListNode;
if (lastListNode != null) {
lastListNode.right = curNode;
}
lastListNode = curNode;
if (curNode.right != null) {
lastListNode = rConvert(curNode.right, lastListNode);
}
return lastListNode;
}