帮你从算法角度来认识二叉树---（三）

引言在上文提到了通过前序遍历中序遍历、后序遍历中序遍历来构建二叉树这篇来帮大家认识一下其他常见的二叉树操作二叉树节点数思路依旧是递归这次是整个二叉树节点个数 左子树节点个数 右子树节点个数 1而左子树节点个数和右子树节点个数也是求当自己为 “ 根节点 ” 是左子树节点个数 右子树节点个数 1代码public int countNodes(TreeNode root){ if(rootnull) return 0; return 1countNodes(root.left)countNodes(root.right); }是否为平衡二叉树思路首先先回忆一下平衡二叉树的定义左右子树高度1这样我们就好写了直接求左子树和右子树的高度用 if 判断高度还是用递归来实现代码public boolean isBalanced(TreeNode root){ if(rootnull) return true; int leftgetHeight(root.left); int rightgetHeight(root.right); return Math.abs(left,right)1 isBalanced(root.left) isBalanced(root.right); } public int getHeight(TreeNode root){ if(rootnull) return 0; int leftgetHieght(root.left); int rightgetHeight(root.right); return Math.max(left,right)1; }翻转二叉树思路依旧是递归思想不断的交换左右子树即可代码public TreeNode invertTree(TreeNode root){ if(rootnull) return null; TreeNode temproot.left; root.leftroot.right; root.righttemp; invertTree(root.left); invertTree(root.right); return root; }判断是否为对称二叉树给你一个二叉树的根节点检查它是否为轴对称思路对称的意思是左子树的左孩子右子树的右孩子左子树的右孩子右子树的左孩子依旧用到了递归思想调用对比函数来看根节点的左右子树是否对称而在对比函数里面使用了递归不断地递归看是否对称代码public boolean isSymmetric(TreeNode root){ if(rootnull) return true; TreeNode leftroot.left; TreeNode rightroot.right; return search(left,right); } public boolean search(TreeNode left,TreeNode right){ if(leftnull rightnull){ return true; } if(leftnull || rightnull){ return false; } if(left.val!right.val){ return false; } return search(left.left,right.right) search(left.right,right.left); }小舟有话说这些题都比较常见无一例外都用到了递归思想大家勤加练习~