给定一个二叉树，从左到右，找出第 k 个叶子节点 [# 65]

问题：

给定一个二叉树，从左到右，找出第 k 个叶子节点。比如

图中二叉树的第 3 个叶子节点（从左到右）是 11.

分析：

因为顺序是从左往右数，所以，对于一个节点下的两个叶子节点来讲（比如 6 下面有两个叶子节点 5 和 11），我们要确保先遍历最左边一个，然后再遍历右边一个。这样，其实，在中序遍历，前序遍历和后序遍历中，都能保证左边叶子节点比右边叶子节点先被遍历。我们只需要对每一个遍历的节点进行检查，看是否是叶子节点，是，则把个数+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