Posted by lily on April 7, 2023

树相关概念:

  1. 节点的度:一个节点含有的子树的个数称为该节点的度;
  2. 树的度:一棵树中,最大的节点度称为树的度;
  3. 叶节点或终端节点:度为零的节点;
  4. 非终端节点或分支节点:度不为零的节点;
  5. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
  6. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
  7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
  8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
  9. 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;
  10. 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;
  11. 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
  12. 节点的祖先:从根到该节点所经分支上的所有节点;
  13. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  14. 森林:由m(m>=0)棵互不相交的树的集合称为森林;

    父亲节点与子节点关系

二叉树的遍历方式

非递归方式

风格不统一遍历法


// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        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();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

风格统一

中序遍历

中序遍历的顺序是左子树 –> 根节点 –> 右子树,在访问左子树和右子树时也以同样的方式访问节点。 先找到左子树的最左节点,再加入中点,再到右节点(作为根节点继续遍历)

class Solution {
// 中序遍历找到第k小个数
    public int kthSmallest(TreeNode root, int k) {

        // 栈迭代中序遍历

        Deque<TreeNode> st = new ArrayDeque<>();

        while (root !=null || !st.isEmpty()){

            // 先遍历左子树

            while (root !=null){

                st.push(root);

                root = root.left;

            }

            // 拿到根节点,此时开始按大小顺序遍历得到数

            root = st.pop();

            k--;

            // 此时是否遍历到了最小k数

            if (k == 0){

                break;

            }

            // 记录右子树根节点

            root = root.right;

            // st.push(root);

        }

        return root.val;

    }

}

层次遍历

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;
        // 收集结果
        if (resList.size() < deep) {
            //当层级增加时,list的Item也增加,利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
		// 层序遍历
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

自上向下

自下而上

通用算法

深度优先

广度优先

广搜和深搜都只是两种不同的搜索方式,给做题的时候提供遍历的思路,对于遍历过的内容,以及要解决的问题,可以由这种搜索方式提供解决思路。 而迭代法和递归法则是实现这两种(深搜广搜)算法的实现方式,既可以由迭代+栈进行深搜,也可以通过递归实现深搜;可以用迭代+队列实现广搜(层次遍历入队列形式)

二叉树分类

二叉搜索树

定义

二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树:

  • 1) 若左子树非空,则左子树上所有结点关键字均小于根结点的关键字值;
  • 2) 若右子树非空,则右子树上所有结点关键字均大于根结点的关键字值;
  • 3) 左、右子树本身也分别是一棵二叉排序树。

由定义可知,二叉排序树是一个递归的数据结构,可以方便的使用递归算法对二叉排序树进行各种运算。根据二叉树的定义,可得左子树结点值 < 根结点值 < 右子树结点值。 所以,对二叉排序树进行中序遍历,可以得到一个递增的有序序列。

如何构建

由于二叉搜索树的中序遍历是升序的,所以可以在序列中选出一个数作为根节点,该数左边的数用来构建左子树,右边的数用来构建右子树。这样可以得到一颗二叉搜索树。 具体可以用递归的方式来分别构建左右子树 递归构建伪代码:

// 输入:一个有序数组,代表平衡二叉树搜索树节点的值
public TreeNode dfs(子树构建范围:int[] nums, int l, int r){
	// 终止条件:子树为空
	if (l>r){
		return null;
	}
	// 寻找根节点-> 在数组中的位置
	int mid = num[l+(r-l)/2];
	// 构造根节点
	TreeNode root = new TreeNode(mid);
	root.left = dfs(左子树范围);
	root.rigth = dfs(右子树范围);
	// 返回最后选中的节点
	return root;
}

平衡二叉树

定义

平衡二叉树是左子树与右子树的最高深度不超过1的二叉树