二叉树小结

发表于 | 分类于 | |

​ 本科在学习数据结构时学起来就一直很吃力，特别是对于树和图的掌握不是特别牢固。在刷LeetCode关于二叉树的额题目基本束手无力。所以就趁机把二叉树的知识进行回顾，并且总结。找的是斯坦福大学的一位教授写得笔记，通俗易懂，也将几个题目事先按照自己的思路先写一写，再与参考答案进行对照。具体见最后附录。

二叉树

​ 每颗二叉树都是由若干个节点组成的，每个节点又是一个结构体，包含左指针，右指针，以及节点的值。其中左、右指针递归地指向一颗新的子树。

定义如下：

1
2
3
4
5
6
struct TreeNode{
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x):val(x),left(nullptr),right(nullptr){};//构造新节点
}

排序二叉树 （BST）

​ 排序二叉树除了满足上述二叉树的定义之外，还需要再附加一个约束条件：左子树的值<=根节点<=右子树的值。排序二叉树主要可以大大地降低搜索时间，从O(n)降到O(logn).

思考策略

​ 当处理二叉树时，主要集中精力思考两件事情：

  • 弄清节点的结构以及如何处理

  • 如何进行递归解决和遍历整棵树

    遵循以下三个思维步骤：

  1. 考虑空值

    （一定要先考虑值为空的处理方法，因为这也是一般递归结束的出口）

  2. 处理节点(node)
  3. 递归处理左右子树(left,right)

    要改掉if(非空)的写法，空值都是递归函数里进行处理了，没必要再多此一举

    （2，3有时会对调）

简而言之三部曲：①：判空 ；②： 看当前；③：看子树

常见问题

  1. 查找（LookUp）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int lookup(TreeNode *root, int target)
    {
        //1.BaseCase empty,处理空值
        if (!root)
            return false;
        else
        {
            //2.处理节点值，如果节点值刚好是要查找的
            if (target == root->val) 
                return true;
            //3.如果不是，那么递归处理子树
            else{
                if(target<root->val)
                    return lookup(root->left,target);
                else
                    return lookup(root->right,target);
            }
        }
    }

    ​

  2. 插入（insert）

    ​ 跟查找相比，插入操作需要修改原来的树结构，也就是需要修改指针值。这里采用一种函数调用的方法解决，而不采用c++的引用。

    1
    root = change(root)

    ​ 所以插入操作需要有一个辅助函数（helper function）来负责创建一个节点，并且返回该节点的指针，其实就是上述二叉树定义代码中的TreeNode(int x)所实现的功能。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    TreeNode *insert(TreeNode *root, int data)
    {
        //1. 树为空，直接创建并返回这个节点
        if (!root)
            return new TreeNode(data);
            //2. 处理子树
        else
        {
            if (data <= root->val)
                root->left = insert(root->left, data);
            else
                root->right = insert(root->right, data);
            //3.处理当前节点
            return root;
        }

    }
    3.建树（Build123）
    1
    2
    3
    4
    5
    6
    7
    TreeNode *build123()
    {
        TreeNode *root = new TreeNode(2);
        root->left = new TreeNode(1);
        root->right = new TreeNode(3);
        return root;
    }
    1. 节点数（Size）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int size(TreeNode *root)
    {
        if (!root)
            return 0;
        else
        {
            return size(root->left) + size(root->right) + 1;
        }
    }
    1. 最深深度（maxDepth）
    1
    2
    3
    4
    5
    6
    7
    8
    int maxDepth(TreeNode *root)
    {
        if (!root)
            return 0;
        else
            return max(maxDepth(root->left), maxDepth(root->right)) + 1;

    }
    1. 最小值（minValue）
    1
    2
    3
    4
    5
    6
    7
    int minValue(TreeNode *root)
    {
        TreeNode *node = root;
        while (node->left)
            node = root->left;
        return node->val;
    }
    1. 递增打印（printTree）
    1
    2
    3
    4
    5
    6
    7
    8
    void printTree(TreeNode *root)
    {
        if (!root)
            return;
        printTree(root->left);
        cout << root->val;
        printTree(root->right);
    }
    1. 自底向上打印
    1
    2
    3
    4
    5
    6
    7
    8
    void printPostorder(TreeNode *root)
    {
        if (!root)
            return;
        printPostorder(root->left);
        printPostorder(root->right);
        cout << root->val;
    }
    1. 路径之值（hasPathSum）
    1
    2
    3
    4
    5
    6
    7
    8
    int hasPathSum(TreeNode *root, int sum)
    {
        if (!root)
            return sum == 0;
        else
            return    hasPathSum(root->left, sum - root->val) 
                   || hasPathSum(root->right, sum - root->val);
    }
    1. 打印所有路径（printPath）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    //8.path
    void printPathRecur(TreeNode *root, vector<int> v)
    {
        if (!root)
            return;
    	//如果是叶子节点，加入vector后输出数组
        if ((!root->left) && (!root->right))
        {
            v.push_back(root->val);
            for (auto i:v)
                cout << i << " ";
            cout << endl;
        }
        //如果非叶子节点，则加入vector，然后继续遍历左右子树
        else
        {
            v.push_back(root->val);
            printPathRecur(root->left, v);
            printPathRecur(root->right, v);
        }
    }

    void printPath(TreeNode *root)
    {
        vector<int> v;
        printPathRecur(root, v);
    }
    1. 镜对称（mirror）
    1
    2
    3
    4
    5
    6
    7
    8
    void mirror(TreeNode *root)
    {
        if (!root)
            return;
        mirror(root->left);
        mirror(root->right);
        swap(root->left, root->right);
    }
    1. 双层树（doubleTree）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void doubleTree(TreeNode *root)
    {
        if (!root)
            return;;

        doubleTree(root->left);
        doubleTree(root->right);

        TreeNode *newNode = new TreeNode(root->val);
        newNode->left = root->left;
        root->left = newNode;
    }
    1. 相同树（sameTree）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int sameTree(TreeNode *a, TreeNode *b)
    {
        //都为空，返回真
        if (!a && !b)
            return true;
        //都不空，则比较
        if (a && b)
        {
            return a->val == b->val
                   && sameTree(a->left, b->left)
                   && sameTree(a->right, b->right);
        } else//一个为空一个非空，返回false
        {
            return false;
        }
    }
    1. 是否为二叉树（isBST）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int isBSTUtil(TreeNode *root, int min, int max)
    {
        if (!root)
            return true;
        if (root->val < min || root->val > max)
            return false;
        return
                isBSTUtil(root->left, min, root->val) &&
                isBSTUtil(root->right, root->val, max);
    }

    int isBST(TreeNode *root)
    {
        return isBSTUtil(root, INT_MIN, INT_MAX);
    }

    完！

    ​