剣指プログラミング(12)
10681 ワード
一、二叉木とその中の1つのノードを指定し、中順遍歴順序の次のノードを見つけて返してください.ツリーのノードには、左右のサブノードだけでなく、親ノードへのポインタも含まれています.
二、二叉木が対称かどうかを判断するための関数を実現してください.なお、1つのツリーがこのツリーのミラーと同じである場合は、対称として定義されます.
三、二叉木を上から下へ層ごとに印刷し、同じ層の接点を左から右に出力する.各層に1行出力します.
四、一つの関数を実現して二叉木をジグザグに印刷してください.すなわち、第一行は左から右の順に印刷して、第二層は右から左の順に印刷して、第三行は左から右の順に印刷して、その他の行はこのように押します.
五、二叉検索ツリーを指定し、その中のk番目の大きなノードを見つけてください.たとえば、5/3 7//2 4 6 8の3番目のノードの値は、ノードの数値の大きさ順に4になります.
class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
// ,
if(pNode.right != null) {
TreeLinkNode tmp = pNode.right;
while(tmp.left != null) {
tmp = tmp.left;
}
return tmp;
}
//
while(pNode.next != null) {
if(pNode.next.left == pNode) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
}
二、二叉木が対称かどうかを判断するための関数を実現してください.なお、1つのツリーがこのツリーのミラーと同じである場合は、対称として定義されます.
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//
//
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) {
return true;
}
return isSymmetrical(pRoot.left, pRoot.right);
}
// ,
boolean isSymmetrical(TreeNode node1, TreeNode node2) {
if(node1 == null && node2 == null) {
return true;
}
if(node1 != null && node2 != null) {
if(node1.val == node2.val) {
return isSymmetrical(node1.left, node2.right) && isSymmetrical(node1.right, node2.left);
}
}
return false;
}
}
三、二叉木を上から下へ層ごとに印刷し、同じ層の接点を左から右に出力する.各層に1行出力します.
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
// ,
ArrayList > Print(TreeNode pRoot) {
ArrayList> res = new ArrayList<>();
if(pRoot == null) {
return res;
}
Queue q = new LinkedList<>();
q.add(pRoot);
while(!q.isEmpty()) {
//
int index = 0, size = q.size();
ArrayList inner = new ArrayList<>();
while(index < size) {
TreeNode cur = q.poll();
inner.add(cur.val);
if(cur.left != null) {
q.add(cur.left);
}
if(cur.right != null) {
q.add(cur.right);
}
index++;
}
res.add(inner);
}
return res;
}
}
四、一つの関数を実現して二叉木をジグザグに印刷してください.すなわち、第一行は左から右の順に印刷して、第二層は右から左の順に印刷して、第三行は左から右の順に印刷して、その他の行はこのように押します.
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
// , ,
public ArrayList > Print(TreeNode pRoot) {
ArrayList> res = new ArrayList<>();
if(pRoot == null) {
return res;
}
Queue q = new LinkedList<>();
q.add(pRoot);
boolean flag = true;
while(!q.isEmpty()) {
//
int index = 0, size = q.size();
ArrayList inner = new ArrayList<>();
while(index < size) {
TreeNode cur = q.poll();
inner.add(cur.val);
if(cur.left != null) {
q.add(cur.left);
}
if(cur.right != null) {
q.add(cur.right);
}
index++;
}
if(flag) {
res.add(inner);
flag = false;
}else {
//
ArrayList rev = new ArrayList<>();
int len = inner.size();
for(int i = len - 1; i >= 0; i--) {
rev.add(inner.get(i));
}
res.add(rev);
flag = true;
}
}
return res;
}
}
五、二叉検索ツリーを指定し、その中のk番目の大きなノードを見つけてください.たとえば、5/3 7//2 4 6 8の3番目のノードの値は、ノードの数値の大きさ順に4になります.
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//
int cnt = 0;
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot != null) {
TreeNode tmp;
if((tmp = KthNode(pRoot.left, k)) != null) {
return tmp;
}
cnt++;
if(k == cnt) {
return pRoot;
}
if((tmp = KthNode(pRoot.right, k)) != null) {
return tmp;
}
}
return null;
}
}