二叉树Part01
力扣
|
|
43

二叉树的种类

完全二叉树

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

Pasted image 20240719150100.png

满二叉树

Pasted image 20240719150053.png

二叉搜索树

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

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

Pasted image 20240719150124.png

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

Pasted image 20240719150200.png

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

二叉树的遍历

  • 深度优先

    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

  • 广度优先

    • 层次遍历（迭代法）

  • 前序遍历：中左右

  • 中序遍历：左中右

  • 后序遍历：左右中

Pasted image 20240719150321.png

二叉树的定义

C++

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(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;
    }
}

递归方法论

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

二叉树的递归遍历

前序遍历

  1. 需要当前节点才能继续递归,所以当前节点为一个参数,还需要一个容器来存放遍历的结果,所以第二个参数就是这个容器
  2. 终止条件就是当前节点为空的时候,即已经遍历到最底层了,就return
  3. 单层递归逻辑就是,先取中间值加入到容器中,再遍历左子树,再遍历右子树.

C++

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

Java

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

中序遍历&后序遍历

顺序调换一下就行

二叉树的迭代遍历

用栈来模拟递归,这样可以节约内存

前序遍历

处理的元素的访问的元素顺序一致,都是中间节点

先压右孩子再压左孩子,因为出栈后面顺序是相反的

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

后序遍历

前序是中左右,后序是左右中,所以我们把前序的左右调换个位置,变成中右左,再将其反转一下,就变成左右中了.

中序遍历

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

前序遍历处理的元素是中间节点,访问的元素也是中间节点.

而中序遍历处理的元素是中间节点,而中序遍历先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

总结

此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。

这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

二叉树的统一迭代法

...懒得看了,直接贴一个代码

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

                st.push(node);                          // 添加中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.top();    // 重新取出栈中元素
                st.pop();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

二叉树的层序遍历(广度优先)

迭代法

逻辑:记住每一层的size数,弹出size个元素,而且每弹出一个,就加上弹出元素的子节点.一位数组vec用于保存每一行的值,二维数组resualt用于保存所有行.注意在循环中更新当前节点(cur)的操作是让当前节点为队列顶部前部TreeNode* node = que.front();

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

递归法

# 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

层序遍历习题

102.二叉树的层序遍历

本题为接下来几题的基础

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode *root) {
    queue<TreeNode *> que;
    if (root != NULL)
      que.push(root);
    vector<vector<int>> result;
    while (!que.empty()) {
      vector<int> vec;
      int size = que.size();
      while (size--) {
        TreeNode *node = que.front();
        vec.push_back(node->val);
        que.pop();
        if (node->left) {
          que.push(node->left);
        }
        if (node->right) {
          que.push(node->right);
        }
      }
      result.push_back(vec);
    }
    return result;
  }
};
107.二叉树的层序遍历II

与102并无大异,修改一下层的输出顺序就好了

reverse(res.begin(), res.end());
199.二叉树的右视图

很简单的修改一下层序遍历时,处理每一层的时候什么时候push元素到结果集中就行了.因为是右视图,所以在遍历到每一层的以后一个元素的时候将元素push进结果集就好了

class Solution {
public:
  vector<int> rightSideView(TreeNode *root) {
    queue<TreeNode *> que;
    vector<int> res;
    if (root) {
      que.push(root);
    }
    while (!que.empty()) {
      int size = que.size();
      for (int i = 0; i < size; i++) {
        TreeNode *cur = que.front();
        que.pop();
        if (i == size - 1) {
          res.push_back(cur->val);
        }
        if (cur->left != NULL) {
          que.push(cur->left);
        }
        if (cur->right != NULL) {
          que.push(cur->right);
        }
      }
    }
    return res;
  }
};
637.二叉树的层平均值

没什么难度

class Solution {
public:
  vector<double> averageOfLevels(TreeNode *root) {
    queue<TreeNode *> que;
    if (root) {
      que.push(root);
    }
    vector<double> res;
    while (!que.empty()) {
      int size = que.size();
      double sum = 0;
      for (int i = 0; i < size; i++) {
        TreeNode *cur = que.front();
        que.pop();
        sum += cur->val;
        if (cur->left) {
          que.push(cur->left);
        }
        if (cur->right) {
          que.push(cur->right);
        }
      }
      res.push_back(sum / size);
    }
    return res;
  }
};
429.N叉树的层序遍历

注意这题给的Node定义,子树使用一个Node*类型的vector容器来存放的.所以我们可以通过cur->children来访问这个容器,当然我们也可以使用vector的各种函数,比如size(),又或是用下标来访问元素(子树节点)

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
  vector<vector<int>> levelOrder(Node *root) {
    queue<Node *> que;
    if (root) {
      que.push(root);
    }
    vector<vector<int>> res;
    while (!que.empty()) {
      int size = que.size();
      vector<int> layer;
      for (int i = 0; i < size; i++) {
        Node *cur = que.front();
        que.pop();
        layer.push_back(cur->val);
        for (int j = 0; j < cur->children.size(); j++) {
          if (cur->children[j]) {
            que.push(cur->children[j]);
          }
        }
      }
      res.push_back(layer);
    }
    return res;
  }
};
515.在每个树行中找最大值
class Solution {
public:
  vector<int> largestValues(TreeNode *root) {
    queue<TreeNode *> que;
    if (root) {
      que.push(root);
    }
    vector<int> res;
    while (!que.empty()) {
      int size = que.size();
      int maxValue = INT_MIN;
      while (size--) {
        TreeNode *cur = que.front();
        que.pop();
        if (cur->val > maxValue) {
          maxValue = cur->val;
        }
        if (cur->left) {
          que.push(cur->left);
        }
        if (cur->right) {
          que.push(cur->right);
        }
      }
      res.push_back(maxValue);
    }
    return res;
  }
};
116.填充每个节点的下一个右侧节点指针

思路:对于每层来说,记录下当前节点,在遍历到下一个节点的时候,令上一个节点的next指向当前节点,以此来连接.使用size来判断当前节点是不是本层的最后一个节点,如果是的话就让当前节点指向NULL.

注意节点更新顺序不能为下面这样,举个例子,我当前在根节点,layerHead为root,cur也为root,此时size为0,进入循环,cur->next被更新为NULL,但是下面的layerHead->next = cur;,又把root->next指向自己了

if (size == 0) {
          cur->next = NULL;
        }
        layerHead->next = cur;
        layerHead = cur;

class Solution {
public:
  Node *connect(Node *root) {
    queue<Node *> que;
    if (root) {
      que.push(root);
      root->next = NULL;
    }
    while (!que.empty()) {
      int size = que.size();
      Node* layerHead = que.front();
      while (size--) {
        Node *cur = que.front();
        layerHead->next = cur;
        layerHead = cur;
        if (size == 0) {
          cur->next = NULL;
        }
        que.pop();
        if (cur->left) {
          que.push(cur->left);
        }
        if (cur->right) {
          que.push(cur->right);
        }
      }
    }
    return root;
  }
};

卡哥的版本

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            // vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = que.front(); // 取出一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;

    }
};
117.填充每个节点的下一个右侧节点指针II
用上一题的解法也能跑完测试?!
104.二叉树的最大深度
class Solution {
public:
  int maxDepth(TreeNode *root) {
    queue<TreeNode *> que;
    if (root) {
      que.push(root);
    }
    int layers = 0;
    while (!que.empty()) {
      int size = que.size();
      while (size--) {
        TreeNode *cur = que.front();
        que.pop();
        if (cur->left) {
          que.push(cur->left);
        }
        if (cur->right) {
          que.push(cur->right);
        }
      }
      layers++;
    }
    return layers;
  }
};
111.二叉树的最小深度

没循环一层就让深度加一,碰到一个节点没有左右孩子,说明他就是最小深度的节点,直接返回depth

class Solution {
public:
  int minDepth(TreeNode *root) {
    if (!root) {
      return 0;
    }
    int depth = 0;
    queue<TreeNode *> que;
    que.push(root);
    while (!que.empty()) {
      int size = que.size();
      depth++;
      while (size--) {
        TreeNode *cur = que.front();
        que.pop();
        if (cur->left) {
          que.push(cur->left);
        }
        if (cur->right) {
          que.push(cur->right);
        }
        if (cur->right == NULL && cur->left == NULL) {
          return depth;
        }
      }
    }
    return depth;
  }
};
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
二叉树Part05

							
							

							
二叉树Part04

							
							

							
二叉树Part03

							
							

							
二叉树Part02

							
							

							
栈与队列Part02

							
							

							
栈与队列part01

							
							

							
字符串Part02

							
							

							
字符串Part01

							
							

							
哈希表Part02

							
							

							
哈希表Part01