二叉树【ing】

二叉树

参考:代码随想录

二叉树遍历

前、中、后遍历递归相似,只是根据根节点的命名前中后遍历。但是迭代遍历有点不同

例子:94. 二叉树的中序遍历

递归遍历

  • 中序递归遍历(其他只要修改顺序即可)

    class Solution {
    public:
      void traversal(TreeNode* cur, vector &vec) {
          if(!cur) return;  // 递归终止条件
          traversal(cur->left, vec);  //左
          vec.push_back(cur->val);  //中
          traversal(cur->right, vec);  //右
      }
      vector inorderTraversal(TreeNode* root) {
          vector ans;
          traversal(root,ans);
          return ans;
      }
    };

迭代遍历

  • 前序(中、左、又)迭代遍历,由于栈的性质,先入右节点,再入左节点

    class Solution {
    public:
      vector inorderTraversal(TreeNode* root) {
          vector ans;
          stack stk;
          // 树为空
          if(!root) return ans;
    
          stk.push(root);
          while(!stk.empty()){
              TreeNode* node = stk.top();
              stk.pop();
              ans.push_back(node->val);
              if(node->right) stk.push(node->right);
              if(node->left) stk.push(node->left);
          }
          return ans;
      }
    };
  • 中序

    分析一下为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢,因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。

    那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。

    class Solution {
    public:
      vector inorderTraversal(TreeNode* root) {
          vector ans;
          stack stk;
          TreeNode* cur = root;  // 当前节点指针
    
          while(cur || !stk.empty()) {
              if(cur) {
                  // 一直遍历到最左边
                  stk.push(cur);
                  cur = cur->left; //左
              } else {
                  cur = stk.top();  // 当前节点为栈顶元素,没有左节点的根节点
                  stk.pop();
                  ans.push_back(cur->val);
                  cur = cur->right;
              }
          }
          return ans;
      }
    };
  • 后续(左、右、中),前序修改成(中、右、左)再反转数组即可

    class Solution {
    public:
      vector inorderTraversal(TreeNode* root) {
          vector ans;
          stack stk;
          // 树为空
          if(!root) return ans;
    
          stk.push(root);
          while(!stk.empty()){
              TreeNode* node = stk.top();
              stk.pop();
              ans.push_back(node->val);
              if(node->left) stk.push(node->left);
              if(node->right) stk.push(node->right);
          }
          reverse(result.begin(), result.end()); // 将结果反转
          return ans;
      }
    };

层序遍历

  • 102. 二叉树的层序遍历
    class Solution {
    public:
      vector> levelOrder(TreeNode* root) {
          vector> ans;
          queue que;
          if(root) que.push(root);
          while(!que.empty()) {
              vector vec;
              int size = que.size();  //每一层需要循环该层的节点数目,将左右节点进入队列
              for(int i=0; ival);
                  // 加入子节点
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
              ans.push_back(vec);
          }
    
          return ans;
      }
    };
  • 107. 二叉树的层序遍历 II

    层序遍历之后,进行反转即可

    class Solution {
    public:
      vector> levelOrderBottom(TreeNode* root) {
          vector> ans;
          queue que;
          if(root) que.push(root);
          while(!que.empty()) {
              vector vec;
              int size = que.size();  //每一层需要循环该层的节点数目,将左右节点进入队列
              for(int i=0; ival);
                  // 加入子节点
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
              ans.push_back(vec);
          }
          reverse(ans.begin(),ans.end());
          return ans;
      }
    };
  • 199. 二叉树的右视图

    层序遍历的时候做一次限定

    class Solution {
    public:
      vector rightSideView(TreeNode* root) {
          vector ans;
          queue que;
          if(root) que.push(root);
          while(!que.empty()) {
              int size = que.size();
              for(int i=0; ival);
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
          }
          return ans;
      }
    };
  • 637. 二叉树的层平均值
    public:
      vector averageOfLevels(TreeNode* root) {
          vector ans;
          queue que;
          que.push(root);
    
          while(!que.empty()) {
              double sum  =0.0;
              int size = que.size();
              for(int i=0; ival;
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
              double res = sum / size;
              ans.push_back(res);
          }
    
          return ans;
      }
    };
  • 429. N 叉树的层序遍历
    class Solution {
    public:
      vector> levelOrder(Node* root) {
          vector> ans;
          queue que;
          if(root) que.push(root);
    
          while(!que.empty()) {
              vector vec;
              int size = que.size();
    
              for(int i=0; ival);
                  // 遍历子节点 入队列
                  if(node->children.size()) {
                      for(Node* n : node->children) {
                          if(n) que.push(n);
                      }
                  }
              }
              ans.push_back(vec);
          }
    
          return ans;
      }
    };
  • 515. 在每个树行中找最大值
    class Solution {
    public:
      vector largestValues(TreeNode* root) {
          vector ans;
          queue que;
          if(root) que.push(root);
    
          while(!que.empty()) {
              int res = INT_MIN;
              int size = que.size();
              for(int i=0; ival) ? node->val: res;
                  if(node->left) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
              ans.push_back(res);
          }
          return ans;
      }
    };
  • 116. 填充每个节点的下一个右侧节点指针
  • 117. 填充每个节点的下一个右侧节点指针 II

    两个题目可以用同样的解法

    • 依然生成vector<int> vec之后,再处理
    class Solution {
    public:
        Node* connect(Node* root) {
            if(!root) return root;
    
            queue que;
            que.push(root);
            while(!que.empty()) {
                vector vec;
                int size = que.size();
                for(int i=0; ileft) que.push(node->left);
                    if(node->right) que.push(node->right);
                }
                for(int i=0; inext = vec[i+1];
                }
                vec[vec.size()-1]->next = NULL;
            }
            return root;
        }
    };
    • 直接新建precur结点,空间利用上少了
    class Solution {
    public:
        Node* connect(Node* root) {
            queue que;
            if (root != NULL) que.push(root);
            while (!que.empty()) {
                int size = que.size();
                // vector 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;
    
        }
    };
  • 104.二叉树的最大深度
    • 层序遍历

      class Solution {
      public:
        int maxDepth(TreeNode* root) {
            if (root == NULL) return 0;
            int depth = 0;
            queue que;
            que.push(root);
            while(!que.empty()) {
                int size = que.size();
                depth++; // 记录深度
                for (int i = 0; i < size; i++) {
                    TreeNode* node = que.front();
                    que.pop();
                    if (node->left) que.push(node->left);
                    if (node->right) que.push(node->right);
                }
            }
            return depth;
        }
      };
    • 也可以用递归去做

  • 111.二叉树的最小深度
    • 层序遍历
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if (root == NULL) return 0;
            int depth = 0;
            queue que;
            que.push(root);
            while(!que.empty()) {
                int size = que.size();
                depth++; // 记录最小深度
                for (int i = 0; i < size; i++) {
                    TreeNode* node = que.front();
                    que.pop();
                    if (node->left) que.push(node->left);
                    if (node->right) que.push(node->right);
                    if (!node->left && !node->right) { // 当左右孩子都为空的时候,说明是最低点的一层了,退出
                        return depth;
                    }
                }
            }
            return depth;
        }
    };
    • 递归
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            // 树为空
            if(!root) return 0;
            // 获取左子树和右子树的最小深度
            int left = minDepth(root->left);
            int right = minDepth(root->right);
            // 如果左、右子树其中一个为空
            if(!left || !right) return left+right+1;
            // 左右子树都不为空
            return min(left, right)+1;
        }
    };

226. 翻转二叉树

  • 采用递归,从上往下,不断将左右子树进行翻转

    class Solution {
    public:
      TreeNode* invertTree(TreeNode* root) {
         // 递归终止条件
         if(!root) return root;
    
         swap(root->left, root->right);
    
         invertTree(root->left);
         invertTree(root->right);
    
         return root;
    
      }
    };
  • 迭代法,前序遍历

    class Solution {
    public:
      TreeNode* invertTree(TreeNode* root) {
          if (root == NULL) return root;
          stack st;
          st.push(root);
          while(!st.empty()) {
              TreeNode* node = st.top();              // 中
              st.pop();
              swap(node->left, node->right);
              if(node->right) st.push(node->right);   // 右
              if(node->left) st.push(node->left);     // 左
          }
          return root;
      }
    };
  • 广度优先遍历(层序遍历)

    class Solution {
    public:
      TreeNode* invertTree(TreeNode* root) {
          queue que;
          if (root != NULL) que.push(root);
          while (!que.empty()) {
              int size = que.size();
              for (int i = 0; i < size; i++) {
                  TreeNode* node = que.front();
                  que.pop();
                  swap(node->left, node->right); // 节点处理
                  if (node->left) que.push(node->left);
                  if (node->right) que.push(node->right);
              }
          }
          return root;
      }
    };

101. 对称二叉树

  • 递归

    class Solution {
    public:
      // 比较内外节点是否是对称的
      bool compare(TreeNode* leftn, TreeNode* rightn) {
          // 首先排除空节点的情况
          if (leftn==NULL && rightn==NULL) return true;
          else if(leftn==NULL && rightn!=NULL) return false;
          else if(leftn!=NULL && rightn==NULL) return false;
          // 排除了空节点,再排除数值不相同的情况
          else if(leftn->val != rightn->val) return false;
    
          // 此时就是:左右节点都不为空,且数值相同的情况
          // 此时才做递归,做下一层的判断
          bool outside = compare(leftn->left, rightn->right);
          bool inside = compare(leftn->right, rightn->left);
          bool isSame = outside && inside;
          return isSame;
      }
      bool isSymmetric(TreeNode* root) {
          if(!root) return true;
           return compare(root->left, root->right);
    
      }
    };
  • 迭代(相当于遍历 理解简单)

    class Solution {
    public:
      bool isSymmetric(TreeNode* root) {
          if (root == NULL) return true;
          queue que;
          que.push(root->left);   // 将左子树头结点加入队列
          que.push(root->right);  // 将右子树头结点加入队列
    
          while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
              TreeNode* leftNode = que.front(); que.pop();
              TreeNode* rightNode = que.front(); que.pop();
              if (!leftNode && !rightNode) {  // 左节点为空、右节点为空,此时说明是对称的
                  continue;
              }
    
              // 左右一个节点不为空,或者都不为空但数值不相同,返回false
              if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                  return false;
              }
              que.push(leftNode->left);   // 加入左节点左孩子
              que.push(rightNode->right); // 加入右节点右孩子
              que.push(leftNode->right);  // 加入左节点右孩子
              que.push(rightNode->left);  // 加入右节点左孩子
          }
          return true;
      }
    };

222. 完全二叉树的节点个数

  • 层序遍历求解

    class Solution {
    public:
      int countNodes(TreeNode* root) {
          if(!root) return 0;
          int num = 0;
          queue que;
          que.push(root);
          while(!que.empty()) {
              int size = que.size();
              for(int i=0; ileft) que.push(node->left);
                  if(node->right) que.push(node->right);
              }
          }
          return num;
      }
    };
  • 递归求,和最大深度类似

    class Solution {
    public:
      int countNodes(TreeNode* root) {
          if(!root) return 0;
          int left = countNodes(root->left);
          int right = countNodes(root->right);
          return left+right+1;
      }
    };
  • 利用完全二叉树的性质

    class Solution {
    public:
      int countNodes(TreeNode* root) {
          if (root == nullptr) return 0;
          TreeNode* left = root->left;
          TreeNode* right = root->right;
          int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的,为了下面求指数方便
          while (left) {  // 求左子树深度
              left = left->left;
              leftHeight++;
          }
          while (right) { // 求右子树深度
              right = right->right;
              rightHeight++;
          }
          if (leftHeight == rightHeight) {
              return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2,所以leftHeight初始为0
          }
          return countNodes(root->left) + countNodes(root->right) + 1;
      }
    };

110. 平衡二叉树

暂无评论

发送评论 编辑评论


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