public class BinaryTree<T> {
TreeNode<T> root;
public BinaryTree(T array[]) {
root = createBinaryTree(array, 0);
}
/**
* @param array
* @param i
* <p>
* Description:
* </p>
*/
private TreeNode<T> createBinaryTree(T[] array, int index) {
TreeNode<T> node = null;
if (index < array.length) {
node = new TreeNode<T>(array[index]);
node.left = createBinaryTree(array, index * 2 + 1);
node.right = createBinaryTree(array, index * 2 + 2);
// System.out.println(node.value);
return node;
}
return node;
}
/**
*
* @param root
* @return
* <p>
* Description:二叉树的高度
* </p>
*/
public int getDepth(TreeNode<T> root) {
if (root == null) {
return 0;
}
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
/**
*
* @param root
* @return
* <p>
* Description:查找所有的叶子节点
* </p>
*/
public List<TreeNode<T>> getAllLeafNode(TreeNode<T> root) {
List<TreeNode<T>> list = new ArrayList<TreeNode<T>>();
if (root == null) {
return null;
}
Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode<T> node = queue.poll();
if (node.left == null && node.right == null) {
list.add(node);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return list;
}
/*
* 平衡二叉树：左右子树的高度差<=1
*/
public boolean isBalancedTree(TreeNode<T> root) {
if (root == null) {
return false;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (Math.abs(leftDepth - rightDepth) <= 1) {
return true;
}
return false;
}
public TreeNode<T> reverseTree(TreeNode<T> root) {
if (root == null) {
return null;
}
TreeNode<T> right = root.right;
root.right = reverseTree(root.left);
root.left = reverseTree(right);
return root;
}
/**
* 广度优先遍历
*
* @param root
* <p>
* Description:
* </p>
*/
public void levelOrderTraversal(TreeNode<T> root) {
if (root == null) {
return;
}
Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
TreeNode<T> currentNode = null;
queue.add(root);
while (!queue.isEmpty()) {
currentNode = queue.poll();
System.out.println(currentNode.value);
if (currentNode.left != null) {
queue.add(currentNode.left);
}
if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
}
/**
* 深度优先遍历
*
* @param root
* <p>
* Description:树的先根遍历的非递归实现和深度优先一模一样
* </p>
*/
public void depthOrderTraversal(TreeNode<T> root) {
if (root == null) {
return;
}
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode<T> currentNode = stack.pop();
System.out.println(currentNode.value);
if (currentNode.right != null) {
stack.push(currentNode.right);
}
if (currentNode.left != null) {
stack.push(currentNode.left);
}
}
}
// 先根
public void preOrderTraversal(TreeNode<T> root) {
if (root == null) {
return;
}
System.out.println(root.value);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
// 中根
public void inOrderTraversal(TreeNode<T> root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.println(root.value);
inOrderTraversal(root.right);
}
// 后根
public void postOrderTraversal(TreeNode<T> root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.println(root.value);
}
//后根遍历的非递归 先根 根-->左子树-->右子树 调整为 根--》右子树--》左子树 即为后根的逆序
//后根遍历，左子树--》右子树--》根
public List<TreeNode> postOrderTraversalunrecursive(TreeNode root) {
List<TreeNode> list=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
list.add(node);
if(node.left!=null){
stack.push(node.left);
}
if(node.right!=null){
stack.push(node.right);
}
}
Collections.reverse(list);
return list;
}
public TreeNode<T> getFather(TreeNode<T> root,TreeNode<T> aNode,TreeNode<T> bNode){
if(root ==null || aNode.equals(root) || bNode.equals(root)){
return root;
}
TreeNode<T> left=getFather(root.left, aNode, bNode);
TreeNode<T> right=getFather(root.right, aNode, bNode);
if(left!=null && right !=null){
return root;
}
if(left!=null){
return left;
}
else
return right;
}
public static void main(String args[]) {
Integer a[] = { 1, 2, 3, 4, 5, 6 };
BinaryTree<Integer> tree = new BinaryTree<Integer>(a);
tree.depthOrderTraversal(tree.root);
System.out.println("depth:" + tree.getDepth(tree.root));
tree.levelOrderTraversal(tree.root);
System.out.println("--------------");
tree.preOrderTraversal(tree.root);
System.out.println(tree.isBalancedTree(tree.root));
TreeNode<Integer> reverse = tree.reverseTree(tree.root);
tree.depthOrderTraversal(reverse);
System.out.println("preOrder--------------");
tree.preOrderTraversal(reverse);
System.out.println("inOrder--------------");
tree.inOrderTraversal(tree.root);
System.out.println("preOrder--------------");
tree.postOrderTraversal(tree.root);
}
}
查找所有的左叶子节点
public Set getAllLeftLeafNode(TreeNode<T> root,Boolean flag,Set set){
if(root == null){
return null;
}
if(root.left!=null){
flag=true;
//System.out.println("l:"+root.left.value+","+flag);
getAllLeftLeafNode(root.left,flag,set);
}
if(root.right!=null){
flag=false;
//System.out.println("r:"+root.right.value+","+flag);
getAllLeftLeafNode(root.right,flag,set);
}
if(root.left==null && root.right==null && flag==true){
System.out.println(root.value);
set.add(root);
}
return set;
}
Find Bottom Left Tree Value (Easy)
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
public T findBottomLeftLeaf(TreeNode root){
if(root==null){
return null;
}
Queue<TreeNode> queue=new LinkedList();
queue.add(root);
TreeNode<T> node=null;
while(!queue.isEmpty()){
node=queue.poll();
if(node.right!=null){
queue.add(node.right);
}
if(node.left!=null){
queue.add(node.left);
}
}
return node.value;
}
