评论

收藏

[C++] 树、二叉树、二叉搜索树

编程语言 编程语言 发布于:2021-08-03 13:18 | 阅读数:448 | 评论:0

视频教程:B站、网易云课堂、腾讯课堂
代码地址:Gitee、Github
存储地址:
百度云-提取码:
Google云

  • 1.二叉树的中序遍历
  • 2.二叉树的前序遍历
  • 3.N叉树的后序遍历
  • 4.N叉树的前序遍历
  • 5.N叉树的层序遍历





  • 二叉树的中序遍历
国内站
java版
/*
思路:
*/


/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
国外站
java版
/*
思路:
*/
class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;
    while(cur!=null || !stack.empty()){
      while(cur!=null){
        stack.add(cur);
        cur = cur.left;
      }
      cur = stack.pop();
      list.add(cur.val);
      cur = cur.right;
    }
    return list;
  }
}

/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/




  • 二叉树的前序遍历
国内站
java版
/*
思路:
*/


/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
国外站
java版
/*
思路:
*/
class Solution {
  public List<Integer> preorderTraversal(TreeNode node) {
    List<Integer> list = new LinkedList<Integer>();
    Stack<TreeNode> rights = new Stack<TreeNode>();
    while(node != null) {
      list.add(node.val);
      if (node.right != null) {
        rights.push(node.right);
      }
      node = node.left;
      if (node == null && !rights.isEmpty()) {
        node = rights.pop();
      }
    }
    return list;
  }
}

/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/




  • N叉树的后序遍历
国内站
java版
/*
思路:
*/


/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
国外站
java版
/*
思路:
*/

// Iterative
class Solution {
  public List<Integer> postorder(Node root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    
    Stack<Node> stack = new Stack<>();
    stack.add(root);
    
    while(!stack.isEmpty()) {
      root = stack.pop();
      list.add(root.val);
      for(Node node: root.children)
        stack.add(node);
    }
    Collections.reverse(list);
    return list;
  }
}
// Recursive
class Solution {
  List<Integer> list = new ArrayList<>();
  public List<Integer> postorder(Node root) {
    if (root == null)
      return list;
    
    for(Node node: root.children)
      postorder(node);
    
    list.add(root.val);
    
    return list;
  }
}
/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/




  • N叉树的前序遍历
国内站
java版
/*
思路:
*/


/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
国外站
java版
/*
思路:
*/
//Iterative Solution
class Solution {
  public List<Integer> preorder(Node root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    
    Stack<Node> stack = new Stack<>();
    stack.add(root);
    
    while (!stack.empty()) {
      root = stack.pop();
      list.add(root.val);
      for (int i = root.children.size() - 1; i >= 0; i--)
        stack.add(root.children.get(i));
    }
    
    return list;
  }
}
//Recursive Solution
class Solution {
  public List<Integer> list = new ArrayList<>();
  public List<Integer> preorder(Node root) {
    if (root == null)
      return list;
    
    list.add(root.val);
    for(Node node: root.children)
      preorder(node);
        
    return list;
  }
}

/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/




  • N叉树的层序遍历
国内站
java版
/*
思路:
*/


/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
国外站
java版
/*
思路:
*/
class Solution {
  public List<List<Integer>> levelOrder(Node root) {
      List<List<Integer>> ret = new LinkedList<>();
      
      if (root == null) return ret;
      
      Queue<Node> queue = new LinkedList<>();
      
      queue.offer(root);
      
      while (!queue.isEmpty()) {
        List<Integer> curLevel = new LinkedList<>();
        int len = queue.size();
        for (int i = 0; i < len; i++) {
          Node curr = queue.poll();
          curLevel.add(curr.val);
          for (Node c : curr.children)
            queue.offer(c);
        }
        ret.add(curLevel);
      }
      
      return ret;
    }
}

/*
评价:
优点:
缺点:
*/
python版:
'''
思路:
'''
'''
评价:
  优点:
  缺点:
'''
c++版:
/*
思路:
*/

/*
评价:
优点:
缺点:
*/
一 树、二叉树、二叉搜索树的实现和特性
DSC0000.png
DSC0001.png
DSC0002.png
DSC0003.png
DSC0004.png
DSC0005.png
DSC0006.png
DSC0007.png
DSC0008.png
DSC0009.png
DSC00010.png
DSC00011.png
DSC00012.png
DSC00013.png
DSC00014.png
DSC00015.png

二 实战题目解析:二叉树的中序遍历
DSC00016.png



关注下面的标签,发现更多相似文章