数据结构与算法 | 二叉树(Binary Tree)

二叉树(Binary Tree)

二叉树（Binary Tree）是一种树形数据结构，由节点构成，每个节点最多有两个子节点：一个左子节点和一个右子节点。

代码语言：java复制

	public class TreeNode {
      	 int val;
      	 TreeNode left;
      	 TreeNode right;
      	 TreeNode(int val) { this.val = val; }
    }

"二叉树"（Binary Tree）这个名称的由来是因为二叉树的每个节点最多有两个子节点，一个左子节点和一个右子节点。其中，“二叉”指的是两个，因此“二叉树”表示每个节点最多可以分支成两个子节点。基本定义：

下一部分要写的是二叉树基本遍历代码实现其实可以有多种，思量后用递归实现应该是初接触者比较简洁好理解的方式。为此，在写二叉树下一部分内容之前简单写下基础递归算法，以保证本系列文章承前启后。

递归(Recursion),在数学与计算机科学中对其描述的说法有很多，比如：

指在函数的定义中使用函数自身的方法；
指一种通过重复将问题分解为同类的子问题而解决问题的方法； （PS：这里同类子问题对于于上一种说法就是函数自身）
指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。 （PS：这里描述的基本情况对应于第一种说法中的函数自身了）

当然本文非学术著作"哪种描述比较合适"在此不多做分析，从编码实践的角度第一种说法更为地气一点。

“将问题分解为同类的子问题” 这一点是用递归的方式来解题的关键，这里用个简单的累加和的例子:

设计一个函数，输入参数为 n ，返回 1 2 ...n 的和。

代码语言：java复制

public int sum(int n){
	int result = 0;
	for (int i = 1; i <= n ; i  ) {
		result = result   i; 
	}
	return result;
}

想想初学 C 语言for循环的时候应该都有写过上述代码，从 1开始递增加到 n 这其实是典型的递推。那如果用递归的思路来思考的话：

求 1 2 ..n 的和（问题） -> 就是 n 加上 求 1 2 ..（n-1）的和（同类的子问题）; 其中最基本的情况 1 的和为 1。

代码语言：java复制

public int sum( int n ) {
	if( 1 == n) return 1;
	return n   sum(n-1);
}

可以看到递归的代码实现上是不是非常简洁。大部分初学者思考上比较习惯于递推，如果第一次接触递归角度思考会有些不适应（或者无法独立分析出来递归）也是正常。当慢慢熟悉后，会发现用递归的思路解决某些算法问题往往会非常简单（在本篇接下来的内容中就能发现这点）。

在初学递归过度到熟悉递归这个阶段，笔者建议可以考虑把一些用递推已经解决了的问题用递归的思路尝试解决，习惯递归思路后会打开一片新世界。

二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。在二叉树中，有三种常见的遍历方式，它们分别是前序遍历、中序遍历和后序遍历。

从根节点开始，首先访问根节点，然后按照前序遍历的方式依次访问左子树和右子树。前序遍历通常用于复制一棵树或计算表达式的值。

访问顺序：根节点 -> 左子树 -> 右子树

给你二叉树的根节点 root ，返回它节点值的前序遍历。

从根节点开始，首先按照中序遍历的方式访问左子树，然后访问根节点，最后访问右子树。中序遍历通常用于访问二叉搜索树中的节点，以升序或降序访问节点值。

访问顺序：左子树 -> 根节点 -> 右子树

给定一个二叉树的根节点 root ，返回它的中序遍历。

针对后序遍历（Postorder Traversal）从根节点开始，首先按照后序遍历的方式访问左子树，然后访问右子树，最后访问根节点。后序遍历通常用于释放二叉树的内存，或计算表达式的值。访问顺序：左子树 -> 右子树 -> 根节点，在此不过多描述相信一定能够完成编码。

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

本系列文章中已经介绍了链表、递归、二叉树，解决算法问题往往会需要综合应用。不妨来看下下面这个问题：

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

0 人点赞