二叉树理论基础

文章：1. 二叉树理论基础

视频：关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩_bilibili

种类

满二叉树

定义：如果一颗二叉树上只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

深度为k，节点数：2^k-1

除了底层以外，从左到右其他地方都是满的，是完全二叉树

完全二叉树

定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含 1 ~ 2^(h-1)个节点。

优先级队列->堆是完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的数都是没有数值的，而二叉搜索树是有数值的。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉搜索树

性质：它是一棵空树或它的左右两个子树的高度的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

左子树和右子树的高度的差不超过1，且按元素中的值进行排序

存储方式

链式存储

链表

线性存储（顺序存储）

数组，找左孩子2 * i +1，右孩子2 * i +1（i为下标）

遍历方式

深度优先遍历：先往深走，遇到叶子节点再往回走。

一般递归实现，

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

迭代法、递归法

广度优先搜索：一层一层的去遍历。

层序遍历（迭代法）

定义方式

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x):val(x),lent(NULL),right(NULL){}
}

二叉树的定义和链表是差不多的，相对于链表，二叉树的节点里多了一个指针，有两个指针，指向左右孩子。

总结

介绍了二叉树的种类、存储方式、遍历方式以及定义。

其他语言版本

Java

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;
	}
}

type TreeNode struct{
	val int
	Left *TreeNode
	Right *TreeNode
}

二叉树的递归遍历

文章：

视频：每次写递归都要靠直觉？这次带你学透二叉树的递归遍历！| LeetCode：144.前序遍历，145.后序遍历，94.中序遍历_哔哩哔哩_bilibili

【思路】

递归三部曲：

1.确定递归函数的参数和返回值

2.确定终止条件：遇到终结点（NULL）

3.确定单层递归的逻辑

前中后序的顺序按照其对应的位置来写。

前序遍历

题目：144. 二叉树的前序遍历

Java实现

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<Integer>();
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer>result){
        if(root ==null){
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }
}

Go实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode){
        if node == nil{
            return 
        }
        res = append(res,node.Val)
        traversal(node.Left)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

中序遍历

题目：94. 二叉树的中序遍历

Java实现

/**
 * 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> res = new ArrayList<>();
        traversal(root,res);
        return res;
    }
    public void traversal(TreeNode node,  List<Integer> res){
        if(node == null){
            return;
        }
        traversal(node.left,res);
        res.add(node.val);
        traversal(node.right,res);
    }
}

Go实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode){
        if node == nil{
            return 
        }
        traversal(node.Left)
        res = append(res,node.Val)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

后序遍历

题目：145. 二叉树的后序遍历

Java实现

/**
 * 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> res = new ArrayList<>();
        preLast(root,res);
        return res;
    }
    public void preLast(TreeNode root,List<Integer> res){
        //左右中
        if (root == null){
            return;
        }
        preLast(root.left,res);
        preLast(root.right,res);
        res.add(root.val);
    }
}

Go实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode){
        if node == nil{
            return 
        }
        traversal(node.Left)
        traversal(node.Right)
        res = append(res,node.Val)
    }
            traversal(root)
    return res
}

二叉树的迭代遍历

文章：3. 二叉树的迭代遍历

视频：写出二叉树的非递归遍历很难么？这次让你不再害怕非递归！|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中序_哔哩哔哩_bilibili

前序遍历：中左右

迭代法：使用栈，先放右孩子，再放左孩子

Java实现

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer>res = new ArrayList<Integer>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        //前序遍历：中左右，因此我们需要按照中右左的方式将其入栈
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return res;
    }
    
}

Go实现

func preorderTraversal(root *TreeNode) []int {
    ans := []int{}

	if root == nil {
		return ans
	}

	st := list.New()
    st.PushBack(root)

    for st.Len() > 0 {
        node := st.Remove(st.Back()).(*TreeNode)

        ans = append(ans, node.Val)
        if node.Right != nil {
            st.PushBack(node.Right)
        }
        if node.Left != nil {
            st.PushBack(node.Left)
        }
    }
    return ans
}

后序遍历：左右中

后序遍历：左右中前序遍历为中左右(入栈顺序为中右左)，我们需要进行入栈操作：中左右（出栈才能为中右左）
然后再反转，即得到了左右中

Java实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        //后序遍历：左右中 前序遍历为中左右(入栈顺序为中右左)，我们需要进行入栈操作：中左右（出栈才能为中右左）
        //然后再反转，即得到了左右中
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

Go实现

func postorderTraversal(root *TreeNode) (res []int) {
    if root == nil{
        return res
    }
    ans := []int{}

    st := list.New()
    st.PushBack(root)

    for st.Len() > 0{
        node := st.Remove(st.Back()).(*TreeNode)

        ans = append(ans,node.Val)
        if node.Left != nil{
            st.PushBack(node.Left)
        }
        if node.Right != nil{
            st.PushBack(node.Right)
        }
    }
    reverse(ans)
    return ans
}
func reverse(a[]int){
    l,r := 0,len(a)-1
    for l < r {
        a[l],a[r] = a[r],a[l]
        l,r = l+1,r-1
    }
}

中序遍历：左中右

处理二叉树：
- 访问节点：遍历二叉树
- 处理节点：将值放入数组中
Java实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }   
        Stack<TreeNode>stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                //一路向左
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                res.add(cur.val);
                cur= cur.right;
            }
        }
        return res;
    }
}

Go实现

获得一个内置链表： st := list.New()

添加一个元素到栈堆顶： st.PushBack(val)

弹出并获取栈堆顶的元素： st.Remove(st.Back()) //链表的末尾元素

func inorderTraversal(root *TreeNode) (res []int) {
    ans := []int{}
    if root == nil{
        return ans
    }
    st := list.New()
    cur := root
    for cur != nil || st.Len() > 0{
        if cur != nil{
            st.PushBack(cur)
            cur = cur.Left
        }else{
            cur = st.Remove(st.Back()).(*TreeNode)
            ans = append(ans,cur.Val)
            cur = cur.Right
        }
    }
    return ans
}

二叉树的统一迭代法

将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

前序遍历

Java实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>result = new LinkedList<>();
        Stack<TreeNode>stack = new Stack<>();
        if(root != null)stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                stack.pop();
                if(node.right!=null)stack.push(node.right);
                if(node.left!= null)stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else{
                stack.pop();
                node = st.peek();
                stack.pop();
                result.add(node.val);
            }
        }
        return result;
    }
}

Go实现

func preorderTraversal(root *TreeNode) []int {
    if root == nil{
        return nil
    }
    var stack = list.New()
    res := []int{}
    stack.PushBack(root);
    var node *TreeNode
    for stack.Len()>0{
        e := stack.Back()
        stack.Remove(e)
        if e.Value == nil{
            e = stack.Back()
            stack.Remove(e)
            node = e.Value.(*TreeNode)
            res = append(res,node.Val)
            continue
        }
        node = e.Value.(*TreeNode)
        if node.Right != nil{
            stack.PushBack(node.Right)
        }
        if node.Left!=nil{
            stack.PushBack(node.Left)
        }
        stack.PushBack(node)
        stack.PushBack(nil)
    }
    return res
}

中序遍历

Java实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>res = new LinkedList<>();
        Stack<TreeNode>st = new Stack<>();
        if(root != null)st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.peek();
            if(node != null){
                st.pop();
                if(node.right != null)st.push(node.right);
                st.push(node);
                st.push(null);
                
                if(node.left != null)st.push(node.left);
            }else{
                st.pop();
                node = st.peek();
                st.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

Go实现

func inorderTraversal(root *TreeNode) []int {
    if root==nil{
       return nil
    }
    stack:=list.New()//栈
    res:=[]int{}//结果集
    stack.PushBack(root)
    var node *TreeNode
    for stack.Len()>0{
        e := stack.Back()
        stack.Remove(e)
        if e.Value==nil{// 如果为空，则表明是需要处理中间节点
            e=stack.Back()//弹出元素（即中间节点）
            stack.Remove(e)//删除中间节点
            node=e.Value.(*TreeNode)
            res=append(res,node.Val)//将中间节点加入到结果集中
            continue//继续弹出栈中下一个节点
        }
        node = e.Value.(*TreeNode)
        //压栈顺序：右中左
        if node.Right!=nil{
            stack.PushBack(node.Right)
        }
        stack.PushBack(node)//中间节点压栈后再压入nil作为中间节点的标志符
        stack.PushBack(nil)
        if node.Left!=nil{
            stack.PushBack(node.Left)
        }
    }
    return res
}

后序遍历

Java实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer>list = new LinkedList<>();
         Stack<TreeNode>st = new Stack<>();
         if(root != null)st.push(root);
         while(!st.isEmpty()){
             TreeNode node = st.peek();
             if(node!= null){
                 st.pop();
                 st.push(node);
                 st.push(null);
                 if(node.right!=null)st.push(node.right);
                 if(node.left!=null)st.push(node.left);
             }else{
                 st.pop();
                 node = st.peek();
                 st.pop();
                 list.add(node.val);
             }
         }
         return list;
    }
}

Go实现

//后续遍历：左右中
//压栈顺序：中右左
func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var stack = list.New()//栈
    res:=[]int{}//结果集
    stack.PushBack(root)
    var node *TreeNode
    for stack.Len()>0{
        e := stack.Back()
        stack.Remove(e)
        if e.Value==nil{// 如果为空，则表明是需要处理中间节点
            e=stack.Back()//弹出元素（即中间节点）
            stack.Remove(e)//删除中间节点
            node=e.Value.(*TreeNode)
            res=append(res,node.Val)//将中间节点加入到结果集中
            continue//继续弹出栈中下一个节点
        }
        node = e.Value.(*TreeNode)
        //压栈顺序：中右左
        stack.PushBack(node)//中间节点压栈后再压入nil作为中间节点的标志符
        stack.PushBack(nil)
        if node.Right!=nil{
            stack.PushBack(node.Right)
        }
        if node.Left!=nil{
            stack.PushBack(node.Left)
        }
    }
    return res
}