遍历思路与子问题思路：详解二叉树的基本操作 （一）+ https://developer.aliyun.com/article/1520508?spm=a2c6h.13148508.setting.14.61564f0e51sYB8
2、获取叶子节点的个数
遍历思路
用成员变量leafCount标记叶子节点的数目。当左子树与右子树都为null时，这个结点是叶子结点，此时令leafCount++即可。
//获取叶子节点的个数 int leafCount; public void getLeafNodeCount3(TreeNode root) { if(root == null) { return; } if(root.left == null && root.right == null) { leafCount++; } getLeafNodeCount(root.left); getLeafNodeCount(root.right); }
子问题思路
整棵二叉树的叶子结点个数 = 左子树的叶子结点个数+右子树的叶子结点个数
叶子结点 = 左子树和右子树都为null的结点
掌握这两个结论，可以写出如下代码：
//获取叶子节点的个数 public int getLeafNodeCount2(TreeNode root) { if(root == null) { return 0; } if(root.left == null && root.right == null) { return 1; } int left = getLeafNodeCount2(root.left); //左子树中叶子节点的个数 int right = getLeafNodeCount2(root.right); //右子树中叶子节点的个数 return left+right; }
或
//获取叶子节点的个数 public int getLeafNodeCount(TreeNode root) { if(root == null) { return 0; } int left = getLeafNodeCount(root.left); int right = getLeafNodeCount(root.right); if(left == 0 && right == 0) { return 1; } return left+right; }
从结果上看。两段代码都是正确的。
注意：在一些问题上，子问题的思路分析能够使问题变得更清晰、简便。
3、获取第K层结点的个数
子问题思路
该题的思路比较巧妙。要求第K层的结点个数，一整棵树的第K层 = 它的左子树的第K-1层 = 它的右子树的第K-1层。
一棵树第K层的结点个数 = 左子树第K-1层的结点个数+右子树第K-1层的结点个数。
可以写出如下代码，如果对代码不理解，可以参照前序遍历的图示将递归画图展开。
1. //获取第k层结点的个数 public int getKLevelNodeCount(TreeNode root,int k) { if(root == null) { return 0; } if(k == 1) { return 1; } int left = getKLevelNodeCount(root.left,k-1); int right = getKLevelNodeCount(root.right,k-1); return left+right; }
4、求树的高度
子问题思路
根据二叉树高度的定义：树的高度或深度是树中结点的最大层次。
一棵二叉树的高度 = 左子树高度与右子树高度的最大值 + 1
由此通项公式，可以写出求二叉树高度的代码：
//二叉树的高度 public int getHeight(TreeNode root) { if(root == null) { //空树高度为0 返回0 return 0; } int left = getHeight(root.left); //记录左子树的高度 int right = getHeight(root.right); //记录右子树的高度 return Math.max(left,right) + 1; //返回左子树和右子树的高度的最大值+1，即树的高度 }
特别注意：若不用变量left和right保存左右子树的高度递归结果，而是直接将递归语句代入求最大值的语句，是不合适的：
虽然在本地IDE中运行，结果不会有错，但在在线OJ中运行，会超出时间限制。因为没有用额外的变量来保存递归结果的话，最终return语句中实际上有四个递归语句，有大量的递归的重复计算，这是非常耗时的。
复杂度分析
时间复杂度：O(N)，每一个结点都要求一次以它为根的树的高度，也就是每一个结点实际都会访问的。
空间复杂度：O(height)，和树的高度有关系。若是单分支的树，则高度为N，空间复杂度即为O(N)，若是满二叉树，则高度为logN，空间复杂度即为O(logN。
5、二叉树的中序遍历
与前面前序遍历的代码相似，只是改变了对元素的操作与递归左右子树的顺序（左根右）。
遍历思路
//中序遍历 递归 遍历思路 public void inOrder(TreeNode root) { if(root == null) { return; } inOrder(root.left); System.out.print(root.value + " "); inOrder(root.right); }
子问题思路
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null) { return list; } List<Integer> left = inorderTraversal(root.left); list.addAll(left); list.add(root.val); List<Integer> right = inorderTraversal(root.right); list.addAll(right); return list; } }
6、二叉树的后序遍历
与前面前序遍历的代码相似，只是改变了对元素的操作与递归左右子树的顺序（左右根）。
遍历思路
//后序遍历 递归 遍历思路 public void postOrder(TreeNode root) { if(root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.value + " "); }
子问题思路
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null) { return list; } List<Integer> left = postorderTraversal(root.left); list.addAll(left); List<Integer> right = postorderTraversal(root.right); list.addAll(right); list.add(root.val); return list; } }
7、检测值为value的元素是否存在，若存在返回该元素的结点
子问题思路
检测值为value的元素在整棵二叉树是否存在 = 检测左树是否存在该节点（如果存在便结束检测并返回） + 检测右树是否存在该结点（如果存在便结束检测并返回）
该代码的思路类似于前序遍历的思路。每遍历到一个结点，就判断这个结点的值是否与给定的value相匹配。
//检测值为value的元素是否存在 子问题思路 public TreeNode find(TreeNode root, int val) { if(root == null) { return null; } if(root.value == val) { return root; } TreeNode left = find(root.left,val); if(left != null) { return left; } TreeNode right = find(root.right,val); return right; }
