相同的树
java">public boolean isSameTree ( TreeNode p, TreeNode q) { if ( p == null && q == null ) { return true ; } else if ( p != null && q != null ) { if ( p. val != q. val) { return false ; } else { return isSameTree ( p. left, q. left) && isSameTree ( p. right, q. right) ; } } return false ;
}
另一棵树的子树
java">public boolean isSameTree ( TreeNode p, TreeNode q) { if ( p == null && q == null ) { return true ; } else if ( p != null && q != null ) { if ( p. val != q. val) { return false ; } else { return isSameTree ( p. left, q. left) && isSameTree ( p. right, q. right) ; } } return false ;
}
public boolean isSubtree ( TreeNode root, TreeNode subRoot) { if ( root == null ) { return false ; } return isSameTree ( root, subRoot) || isSubtree ( root. left, subRoot) || isSubtree ( root. right, subRoot) ;
}
翻转二叉树
java">public TreeNode invertTree ( TreeNode root) { if ( root == null ) { return null ; } TreeNode left = invertTree ( root. left) ; TreeNode right = invertTree ( root. right) ; root. left = right; root. right = left; return root;
}
平衡二叉树
java">
public int getHeight ( TreeNode root) { if ( root == null ) { return 0 ; } return 1 + Math . max ( getHeight ( root. left) , getHeight ( root. right) ) ;
}
public boolean isBalanced ( TreeNode root) { if ( root == null ) { return true ; } if ( Math . abs ( getHeight ( root. left) - getHeight ( root. right) ) > 1 ) { return false ; } return isBalanced ( root. left) && isBalanced ( root. right) ;
}
public int getHeight ( TreeNode root) { if ( root == null ) { return 0 ; } int leftHeight = getHeight ( root. left) ; int rightHeight = getHeight ( root. right) ; if ( leftHeight == - 1 || rightHeight == - 1 || Math . abs ( leftHeight - rightHeight) > 1 ) { return - 1 ; } return 1 + Math . max ( leftHeight, rightHeight) ;
}
public boolean isBalanced ( TreeNode root) { return getHeight ( root) >= 0 ;
}
对称二叉树
java">public boolean isSymmetricHelper ( TreeNode left, TreeNode right) { if ( left == null && right == null ) { return true ; } else if ( left != null && right != null ) { if ( left. val != right. val) { return false ; } else { return isSymmetricHelper ( left. left, right. right) && isSymmetricHelper ( left. right, right. left) ; } } return false ;
}
public boolean isSymmetric ( TreeNode root) { if ( root == null ) { return true ; } return isSymmetricHelper ( root. left, root. right) ;
}
二叉树遍历
java">class TreeNode { public char val; public TreeNode left; public TreeNode right; public TreeNode ( char val) { this . val = val; }
} public class Main { public static int i; public static TreeNode createTree ( String str) { TreeNode root = null ; char c = str. charAt ( i++ ) ; if ( c != '#' ) { root = new TreeNode ( c) ; root. left = createTree ( str) ; root. right = createTree ( str) ; } return root; } public static void inorder ( TreeNode root) { if ( root == null ) { return ; } inorder ( root. left) ; System . out. print ( root. val + " " ) ; inorder ( root. right) ; } public static void main ( String [ ] args) { Scanner in = new Scanner ( System . in) ; while ( in. hasNextLine ( ) ) { String str = in. nextLine ( ) ; i = 0 ; TreeNode root = createTree ( str) ; inorder ( root) ; System . out. println ( ) ; } }
}
二叉树的层序遍历
public List< List< Integer>> levelOrder ( TreeNode root) { List< List< Integer>> ret = new ArrayList < > ( ) ; if ( root == null) { return ret; } Queue< TreeNode> queue = new LinkedList < > ( ) ; queue. offer ( root) ; while ( ! queue. isEmpty ( ) ) { int size = queue. size ( ) ; List< Integer> row = new ArrayList < > ( ) ; while ( size > 0 ) { TreeNode peek = queue. peek ( ) ; if ( peek. left != null) { queue. offer ( peek. left) ; } if ( peek. right != null) { queue. offer ( peek. right) ; } row. add ( queue. remove ( ) . val) ; -- size; } ret. add ( row) ; } return ret;
}
二叉树的最近公共祖先
public TreeNode lowestCommonAncestor ( TreeNode root, TreeNode p, TreeNode q) { if ( root == null) return root; if ( root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor ( root. left, p, q) ; TreeNode right = lowestCommonAncestor ( root. right, p, q) ; if ( left != null && right != null) { return root; } else if ( left != null) { return left; } else { return right; }
}
public boolean lowestCommonAncestorHelper ( TreeNode root, TreeNode tofind, Stack< TreeNode> stack) { if ( root == null) return false ; stack. push ( root) ; if ( root == tofind) return true ; if ( lowestCommonAncestorHelper ( root. left, tofind, stack) || lowestCommonAncestorHelper ( root. right, tofind, stack) ) { return true ; } else { stack. pop ( ) ; return false ; }
}
public TreeNode lowestCommonAncestor ( TreeNode root, TreeNode p, TreeNode q) { Stack< TreeNode> stack1 = new Stack < > ( ) ; Stack< TreeNode> stack2 = new Stack < > ( ) ; lowestCommonAncestorHelper ( root, p, stack1) ; lowestCommonAncestorHelper ( root, q, stack2) ; while ( stack1. size ( ) > stack2. size ( ) ) { stack1. pop ( ) ; } while ( stack1. size ( ) < stack2. size ( ) ) { stack2. pop ( ) ; } while ( stack1. peek ( ) != stack2. peek ( ) ) { stack1. pop ( ) ; stack2. pop ( ) ; } return stack1. peek ( ) ;
}
从前序与中序遍历序列构造二叉树
public int step = 0 ;
public TreeNode buildTreeHelper ( int [ ] preorder, int [ ] inorder, int start, int end) { if ( start > end) return null; TreeNode root = new TreeNode ( preorder[ step++ ] ) ; int i = 0 ; for ( ; i <= end; i++ ) { if ( inorder[ i] == root. val) { break ; } } root. left = buildTreeHelper ( preorder, inorder, start, i - 1 ) ; root. right = buildTreeHelper ( preorder, inorder, i + 1 , end) ; return root;
}
public TreeNode buildTree ( int [ ] preorder, int [ ] inorder) { return buildTreeHelper ( preorder, inorder, 0 , inorder. length - 1 ) ;
}
从中序与后序遍历序列构造二叉树
public int step;
public TreeNode buildTreeHelper ( int [ ] postorder, int [ ] inorder, int start, int end) { if ( start > end) return null; TreeNode root = new TreeNode ( postorder[ step-- ] ) ; int i = 0 ; for ( ; i <= end; i++ ) { if ( inorder[ i] == root. val) { break ; } } root. right = buildTreeHelper ( postorder, inorder, i + 1 , end) ; root. left = buildTreeHelper ( postorder, inorder, start, i - 1 ) ; return root;
}
public TreeNode buildTree ( int [ ] inorder, int [ ] postorder) { step = postorder. length - 1 ; return buildTreeHelper ( postorder, inorder, 0 , inorder. length - 1 ) ;
}
根据二叉树创建字符串
public String tree2str ( TreeNode root) { if ( root == null) return "" ; StringBuilder str = new StringBuilder ( ) ; str. append ( root. val) ; if ( root. left != null || root. right != null) { str. append ( '(' ) ; str. append ( tree2str ( root. left) ) ; str. append ( ')' ) ; } if ( root. right != null) { str. append ( '(' ) ; str. append ( tree2str ( root. right) ) ; str. append ( ')' ) ; } return str. toString ( ) ;
}
二叉树的前序遍历
public List< Integer> preorderTraversal ( TreeNode root) { List< Integer> list = new ArrayList < > ( ) ; if ( root == null) return list; Stack< TreeNode> stack = new Stack < > ( ) ; TreeNode cur = root; TreeNode top = null; while ( cur != null || ! stack. isEmpty ( ) ) { while ( cur != null) { stack. push ( cur) ; list. add ( cur. val) ; cur = cur. left; } top = stack. pop ( ) ; cur = top. right; } return list;
}
二叉树的中序遍历
public List< Integer> inorderTraversal ( TreeNode root) { List< Integer> list = new ArrayList < > ( ) ; if ( root == null) return list; Stack< TreeNode> stack = new Stack < > ( ) ; TreeNode cur = root; TreeNode top = null; while ( cur != null || ! stack. isEmpty ( ) ) { while ( cur != null) { stack. push ( cur) ; cur = cur. left; } top = stack. pop ( ) ; list. add ( top. val) ; cur = top. right; } return list;
}
二叉树的后序遍历
public List< Integer> postorderTraversal ( TreeNode root) { List< Integer> list = new ArrayList < > ( ) ; if ( root == null) return list; Stack< TreeNode> stack = new Stack < > ( ) ; TreeNode cur = root; TreeNode top = null; while ( cur != null || ! stack. isEmpty ( ) ) { while ( cur != null) { stack. push ( cur) ; cur = cur. left; } top = stack. peek ( ) ; cur = top. right; if ( cur == null) { TreeNode tmp = stack. pop ( ) ; list. add ( tmp. val) ; while ( ! stack. isEmpty ( ) && stack. peek ( ) . right == tmp) { tmp = stack. pop ( ) ; list. add ( tmp. val) ; } } } return list;
}
判断一棵树是不是完全二叉树
boolean isCompleteTree ( TreeNode root) { if ( root == null) { return true ; } Queue< TreeNode> queue = new LinkedList < > ( ) ; queue. offer ( root) ; while ( true ) { TreeNode top = queue. poll ( ) ; if ( top != null) { queue. offer ( top. left) ; queue. offer ( top. right) ; } else { break ; } } while ( ! queue. isEmpty ( ) ) { if ( queue. poll ( ) != null) { return false ; } } return true ;
}