单链表有多个next指针就变成树了。
Linked List是特殊化的Tree,Tree是特殊化的Graph。
没有环的图就是树。
树节点
Java
public class TreeNode{
public int val;
public TreeNode left,right;
public TreeNode(int val){
this.val = val;
this.left = null;
this.right = null;
}
}
C++
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
}
二叉树遍历
1.前序:根-左-右
2.中序:左-根-右
3.后序:左-右-根
遍历基本上基于递归的
def preorder(self,root):
if root:
self traverse_path append(root val)
self preorder(root left)
self preorder(root right)
def inorder(self,root):
if root:
self inorder(root left)
self traverse_path append(root val)
self inorder(root right)
def postorder(self,root)
if root:
self postorder(root left)
self postorder(root right)
self traverse_path append(root val)
二叉搜索树Binary Search Tree
二叉搜索树，也称二叉排序树、有序二叉树、排序二叉树，是指一棵空树或者具有下列性质的二叉树:
1.左子树上所有节点的值均小于它的根节点的值；
2.右子树上的所有节点的值均大于它的根节点的值；
3.依次类推:左、右子树也分别为二叉查找树。(这就是重复性！)
中序遍历:升序遍历
1.查询 log2(n)
2.插入新节点(创建) log2(n)
3.删除
二叉树的中序遍历
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
给定一个二叉树，返回它的中序遍历。
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
方法一:递归法
第一种解决方法是使用递归。这是经典的方法，直截了当。我们可以定义一个辅助函数来实现递归。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
public class Solution {
@Test
public void testBinaryTree(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = inorderTraversal(root);
System.out.printf(res.toString());
}
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper(root,res);
return res;
}
public void helper(TreeNode root,ArrayList<Integer> res){
if(root != null){
if(root.left != null){
helper(root.left,res);
}
res.add(root.val);
if(root.right != null){
helper(root.right,res);
}
}
}
}
//输出
[4, 2, 5, 1, 6, 3]
复杂度分析
时间复杂度：O(n)。递归函数 T(n) = 2 * T(n/2)+1。
空间复杂度：最坏情况下需要空间O(n)O(n)，平均情况为O(\log n)O(logn)。
二叉树.png
方法二:基于栈的遍历
public class Solution {
@Test
public void testStack(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = inorderTraversal0(root);
System.out.printf(res.toString());
}
public List<Integer> inorderTraversal0(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()){
while(curr != null){
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
」
//输出
[4, 2, 5, 1, 6, 3]
复杂度分析
时间复杂度：O(n)O(n)。
空间复杂度：O(n)O(n)。
二叉树的前序遍历
方法一:递归法
class Solution {
@Test
public void testpreorderTravelsal(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = preorderTraversal(root);
System.out.printf(res.toString());
}
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper0(root,res);
return res;
}
public void helper0(TreeNode root,ArrayList<Integer> res){
if(root != null){
res.add(root.val);
if(root.left!=null){
helper0(root.left,res);
}
if(root.right!=null){
helper0(root.right,res);
}
}
}
}
//输出
[1, 2, 4, 5, 3, 6]
方法二:基于栈的遍历
@Test
public void testPreorderTraversalStack0(){
TreeNode root = new TreeNode(1);
TreeNode tree4 = new TreeNode(4);
TreeNode tree5 = new TreeNode(5);
TreeNode tree2 = new TreeNode(2);
TreeNode tree3 = new TreeNode(3);
TreeNode tree6 = new TreeNode(6);
root.left = tree2;
root.right = tree3;
tree2.left = tree4;
tree2.right = tree5;
tree3.left = tree6;
List<Integer> res = preorderTraversal0(root);
System.out.printf(res.toString());
}
public List<Integer> preorderTraversal0(TreeNode root){
ArrayList<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()){
while(curr!= null){
res.add(curr.val);
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return res;
}
//输出
[1, 2, 4, 5, 3, 6]
时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)O(N) ，其中 NN 是节点的个数，也就是树的大小。
空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)O(N)。
N叉树的前序遍历
@Test
public void testPreOrder(){
Node root = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
ArrayList<Node> list = new ArrayList<Node>();
list.add(node3);
list.add(node2);
list.add(node4);
root.children = list;
ArrayList<Node> list0 = new ArrayList<Node>();
list.add(node5);
list.add(node6);
node3.children = list0;
List<Integer> list1 = preorder(root);
System.out.println(list1.toString());
}
public List<Integer> preorder(Node root) {
ArrayList<Integer> res = new ArrayList<Integer>();
Node curr = root;
helper(curr,res);
return res;
}
public void helper(Node curr,ArrayList<Integer> res){
if(curr != null){
res.add(curr.val);
if(curr.children != null && curr.children.size()>0){
for(Node node:curr.children){
helper(node,res);
}
}
}
}
//输出
[1, 3, 2, 4, 5, 6]
二叉树的后序遍历
方法一:递归法
//后序遍历postorder traversal
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
helper0(root,res);
return res;
}
//递归
void helper0(TreeNode node,ArrayList<Integer> res){
if (node!=null){
if (node.left!=null){
helper0(node.left,res);
}
if (node.right!=null){
helper0(node.right,res);
}
res.add(node.val);
}
}
方法二:栈
//栈
public List<Integer> postorderTraversal0(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur!=null){
while (cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
//分两种情况，如果没有右孩子或右孩子被访问过了
if (cur.right == null || (res.size() != 0 && res.get(res.size() - 1).equals(cur.right.val))){
res.add(cur.val);
cur = null;
}else{
stack.push(cur);
cur = cur.right;
}
}
return res;
}
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
输出原始二叉树
//前序遍历
int[] preorder;
HashMap<Integer,Integer> map = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0 || in.length == 0)return null;
this.preorder = pre;
for(int i = 0;i<in.length;i++){
map.put(in[i],i);
}
return helper1(0,0,in.length -1);
}
//pre_root_index:根节点在前序遍历中的下标位置
//in_left_index:该节点在中序遍历中的左边界
//in_right_index:在中序遍历中的右边界
public TreeNode helper1(int pre_root_index,int in_left_index,int in_right_index){
if (in_left_index > in_right_index) return null;
//根节点在中序遍历中的位置in_root_index
int in_root_index = map.get(preorder[pre_root_index]);
//新建节点
TreeNode node = new TreeNode(preorder[pre_root_index]);
//寻找node的左节点
//在前序遍历中的位置就是:根节点的下标+1(右边一个单位)
//在中序遍历中的位置就是:1.左边界不变，2.右边界就是根节点的左边一个单位
node.left = helper1(pre_root_index+1,in_left_index,in_root_index-1);
//寻找node的右节点
//在前序遍历中的位置就是:根节点的下标+左子树的长度+1
//在中序遍历中的位置就是:1.左边界根节点的右边一个单位下标+1，2.右边界不变
node.right = helper1(pre_root_index + in_root_index - in_left_index + 1,in_root_index+1,in_right_index);
return node;
}
