一、二叉树前中后遍历
public class BinaryTree { static class TreeNode{ public char val; public TreeNode left; public TreeNode right; public TreeNode(char val) { this.val = val; } } public TreeNode creatTree(){ TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } //前序遍历 void preOrder(TreeNode root){ //根左右 if(root == null){ return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } //中序遍历 void inOrder(TreeNode root){ //左根右 if(root == null){ return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } //后序遍历 void postOrder(TreeNode root){ //左右根 if(root == null){ return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); } public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); BinaryTree.TreeNode root = binaryTree.creatTree(); binaryTree.preOrder(root); System.out.println(); binaryTree.inOrder(root); System.out.println(); binaryTree.postOrder(root); } }
二、获取节点个数
public int nodeSize; int size(TreeNode root){ if (root == null){ return 0; } nodeSize++; size(root.left); size(root.right); return nodeSize; } //子问题思路解决：整棵树的节点=左子树的节点+右子数的节点+1 int size2(TreeNode root){ if (root == null){ return 0; } return size2(root.left)+size2(root.right)+1; }
三.获取叶子节点个数
public int leafSize; int getLeafNodeCount(TreeNode root){ if (root == null){ return 0; } if (root.left == null && root.right == null){ leafSize++; } getLeafNodeCount(root.left); getLeafNodeCount(root.right); return leafSize; }
四.获取第k层节点个数
public int leveSize; int getleveNodeCount(TreeNode root,int k){ if(root == null){ return 0; } if (k == 1) { return 1; } return getleveNodeCount(root.left,k-1) + getleveNodeCount(root.right,k-1); }
五.求二叉树的高度，时间复杂度O（N）
int getHeight(TreeNode root){ if (root == null){ return 0; } int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); return leftHeight > rightHeight?leftHeight+1:rightHeight+1; }
六.检测值为value的元素是否存在
TreeNode find(TreeNode root,int val){ if (root == null){ return null; } if (root.val == val){ return root; } TreeNode ret1 = find(root.left,val); if (ret1 != null){ return ret1; } TreeNode ret2 = find(root.right,val); if (ret2 != null){ return ret2; } return null; }
七. 检查两颗树是否相同
public boolean isSameTree(TreeNode p, TreeNode q) { if( (p == null && q !=null) || (p != null && q == null) ){ return false; } if(p == null && q == null){ return true; } if(p.val !=q.val){ return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }
八.判断一棵二叉树是不是平衡二叉树
时间复杂度O（N）
public boolean isBalanced(TreeNode root) { if(root == null){ return true; } return getHeight(root)>=0; } int getHeight(TreeNode root) { if (root == null){ return 0; } int leftHeight =getHeight(root.left); if(leftHeight < 0){ return -1; } int rightHeight = getHeight(root.right); if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <=1){ return Math.max(leftHeight,rightHeight)+1; }else{ return -1; } }
九.一个二叉树的根节点 root ， 检查它是否轴对称
检查根节点值是否一样，左数的左和右树的右是否一样，左树的右和右树的左是否一样。
public boolean isSymmetric(TreeNode root) { if(root == null) return true; return isSymmetricChild(root.left,root.right); } private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){ if((leftTree == null && rightTree != null) ||(leftTree != null && rightTree == null)){ return false; } if(leftTree == null && rightTree == null){ return true; } if(leftTree.val != rightTree.val){ return false; } return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left); }
十. 判断subRoot是不是root的子树
//时间复杂度：O(m*n) public boolean isSubtree(TreeNode root,TreeNode subTree) { if(root == null || subTree == null) { return false; } //判断根节点是否相同 if (isSameTree(root,subTree)){ return true; } //判断左子树是否相同 if(isSubtree(root.left, subTree)) { return true; } //判断右子树是否相同 if(isSubtree(root.right, subTree)) { return true; } return false; } public boolean isSameTree(TreeNode p, TreeNode q) { if( (p == null && q !=null) || (p != null && q == null) ){ return false; } if(p == null && q == null){ return true; } if(p.val !=q.val){ return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); }
十一.翻转二叉树
public TreeNode invertTree(TreeNode root){ if(root == null){ return null; } if(root.left == null && root.right == null){ return root; } //交换左右节点 TreeNode tmp = root.left; root.left = root.right; root.right = tmp; //交换左树 invertTree(root.left); //交换右树 invertTree(root.right); return root; }
总结
今天复习二叉树练习。
