二叉木を与え,左から右へk番目の葉ノードを探し出す[#65]

質問:
二叉木を与え,左から右にk番目の葉ノードを見つけた.たとえば
図中の二叉木の3番目の葉ノード(左から右)は11である.
分析:
順番は左から右に数えるので、1つのノードの下にある2つのリーフノードについて(たとえば6の下に2つのリーフノード5と11がある)では、まず一番左の1つを巡り、次に右の1つを巡ります.これにより、実際には、中順遍歴、前順遍歴、後順遍歴では、左のリーフノードが右のリーフノードよりも先に遍歴されることが保証されます.各遍歴ノードをチェックして、リーフノードかどうか、はいを選択すると、個数+1となる.コードは次のとおりです.

public class NthLeaf {
	
	static int k = 0;

	// get the nth leaf by using preorder traversal
	public void getNthleve(Node root, int n) {
		
		if (root == null) return;
		
		if (root.rightChild == null && root.leftChild == null) {
			k++;
			if (k == n) {
				System.out.print(root.toString());
			}
		}

		getNthleve(root.leftChild, n);
		getNthleve(root.rightChild, n);
	}
	
	public static void main(String[] args) {
		 Node a = new Node(2);
	     Node b = new Node(7);
	     Node c = new Node(5);
	     Node d = new Node(2);
	     Node e = new Node(6);
	     Node f = new Node(9);
	     Node g = new Node(5);
	     Node h = new Node(11);
	     Node i = new Node(4);
	     
	     a.leftChild = b;
	     a.rightChild = c;
	     b.leftChild = d;
	     b.rightChild = e;
	     c.rightChild = f;
	     e.leftChild = g;
	     e.rightChild = h;
	     f.rightChild = i;
	     
	     new NthLeaf().getNthleve(a, 3);		
	}
}

class Node {
    Node leftChild = null;
    Node rightChild = null;
    int value;

    Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + "";
    }
}

転載は出典を明記してください.http://blog.csdn.net/beiyeqingteng