当前位置：首页 > news >正文

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

news 2026/7/18 6:55:51

引言

在上文提到了通过前序遍历+中序遍历、后序遍历+中序遍历来构建二叉树，这篇来帮大家认识一下其他常见的二叉树操作

二叉树节点数

思路

依旧是递归，这次是整个二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1，而左子树节点个数和右子树节点个数也是求当自己为 “ 根节点 ” 是左子树节点个数 + 右子树节点个数 + 1

代码

public int countNodes(TreeNode root){ if(root==null) return 0; return 1+countNodes(root.left)+countNodes(root.right); }

是否为平衡二叉树

思路

首先先回忆一下平衡二叉树的定义：左右子树高度<=1，这样我们就好写了，直接求左子树和右子树的高度，用 if 判断，高度还是用递归来实现

代码

public boolean isBalanced(TreeNode root){ if(root==null) return true; int left=getHeight(root.left); int right=getHeight(root.right); return Math.abs(left,right)<=1 && isBalanced(root.left) && isBalanced(root.right); } public int getHeight(TreeNode root){ if(root==null) return 0; int left=getHieght(root.left); int right=getHeight(root.right); return Math.max(left,right)+1; }

翻转二叉树

思路

依旧是递归思想，不断的交换左右子树即可

代码

public TreeNode invertTree(TreeNode root){ if(root==null) return null; TreeNode temp=root.left; root.left=root.right; root.right=temp; invertTree(root.left); invertTree(root.right); return root; }

判断是否为对称二叉树

给你一个二叉树的根节点，检查它是否为轴对称

思路

对称的意思是左子树的左孩子=右子树的右孩子，左子树的右孩子=右子树的左孩子

依旧用到了递归思想，调用对比函数来看根节点的左右子树是否对称，而在对比函数里面，使用了递归，不断地递归看是否对称

代码

public boolean isSymmetric(TreeNode root){ if(root==null) return true; TreeNode left=root.left; TreeNode right=root.right; return search(left,right); } public boolean search(TreeNode left,TreeNode right){ if(left==null && right==null){ return true; } if(left==null || right==null){ return false; } if(left.val!=right.val){ return false; } return search(left.left,right.right) && search(left.right,right.left); }