微信公众号：码云成化
关注可了解更多的教程及进阶技巧。问题或建议，请公众号留言;
如果你觉得阿云对你有所帮助，欢迎赞赏
深度的定义
[ 当前结点的层数。默认叶子节点是 null 节点，深度是 0 。其子节点是 null 节点，深度是 1 。 ]
 普通二叉树
- 给出上图一个普通二叉树，如果计算结点深度，用我们大脑去做的话会怎么做呢？我觉得一般人思路应该是这样的，先把最直观的信息采集起来。
- 那么 [4] 结点的深度、[5] 结点的深度、[3] 结点的深度，因为它们都没有子节点，深度都是 1 。
- 根据 [4] 结点的深度和 [5] 结点的深度，可以求出 [2] 结点的深度，max( [4] 结点的深度, [5] 结点的深度 ) + 1 = 2。
- 有了 [2] 结点的深度和 [3] 结点的深度，可以求出 [1] 结点的深度，max( [2] 结点的深度, [3] 结点的深度 ) + 1 = 3。
深度优先搜索
大多数使用的是递归函数。其实并没有名字所说的那么复杂，使用递归函数对整个目标进行遍历。
递归函数的三要素
- 子问题与原问题做同样的事。
- 需要有一个要递归函数结束的出口。
- 递归表达式。
递归过程
- 求 depth( [1] 结点 ) 必求 depth( [2] 结点 ) 和 depth( [3] 结点 )
- 求 depth( [2] 结点 ) 必求 depth( [4] 结点 ) 和 depth( [5] 结点 )
递归表达式
- depth(rt)=max(depth(rt->left), depth(rt->right))+1;<br>
- package com.pure.common.recursion;<br>/**<br> * @desc: 二叉树深度遍历<br> **/<br>public class DepthUtil {<br> // 结点类<br> public static class TreeNode {<br> private int node;<br> private TreeNode left;<br> private TreeNode right;<br> public TreeNode() {<br> }<br> public TreeNode(int node) {<br> this.node = node;<br> }<br> public int getNode() {<br> return node;<br> }<br> public void setNode(int node) {<br> this.node = node;<br> }<br> public TreeNode getLeft() {<br> return left;<br> }<br> public void setLeft(TreeNode left) {<br> this.left = left;<br> }<br> public TreeNode getRight() {<br> return right;<br> }<br> public void setRight(TreeNode right) {<br> this.right = right;<br> }<br> @Override<br> public String toString() {<br> return "TreeNode{" +<br> "node=" + node +<br> ", left=" + left +<br> ", right=" + right +<br> '}';<br> }<br> }<br> public static void main(String[] args) {<br> TreeNode root$1 = new TreeNode(1);<br> TreeNode node$2 = new TreeNode(2);<br> TreeNode node$3 = new TreeNode(3);<br> TreeNode node$4 = new TreeNode(4);<br> TreeNode node$5 = new TreeNode(5);<br> // 1 结点<br> root$1.setLeft(node$2);<br> root$1.setRight(node$3);<br> // 2 结点<br> node$2.setLeft(node$4);<br> node$2.setRight(node$5);<br> System.out.println("root 结点深度是：" + depth(root$1));<br> System.out.println("node$2 结点深度是：" + depth(node$2));<br> System.out.println("node$3 结点深度是：" + depth(node$3));<br> System.out.println("node$4 结点深度是：" + depth(node$4));<br> System.out.println("node$5 结点深度是：" + depth(node$5));<br> }<br> // 深度递归函数<br> public static int depth(TreeNode root) {<br> if (null == root) {<br> return 0;<br> }<br> int l, r;<br> l = depth(root.getLeft());<br> r = depth(root.getRight());<br> return Math.max(l, r) + 1;<br> }<br>}<br>
- root 结点深度是：3<br>node$2 结点深度是：2<br>node$3 结点深度是：1<br>node$4 结点深度是：1<br>node$5 结点深度是：<br>
希望可以帮到你！相互取暖，共同进步。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
