《LeetCode力扣练习》代码随想录——二叉树（二叉树的统一迭代法—Java）

刷题思路来源于 代码随想录

144. 二叉树的前序遍历

• 二叉树

  /**
   * Definition for a binary tree node.
   * 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;
   *     }
   * }
   */
  class Solution {
      public List<Integer> preorderTraversal(TreeNode root) {
  
          if(root==null){
              return new ArrayList<Integer>();
          }
  
          List<Integer> result=new ArrayList<>();
          Deque<TreeNode> stack=new ArrayDeque<>();
  
          stack.push(root);
  
          while(stack.size()!=0){
  
              TreeNode temp=stack.pop();
  
              if(temp.val!=-101){
  
                  if(temp.right!=null){
                      stack.push(temp.right);
                  }
  
                  if(temp.left!=null){
                      stack.push(temp.left);
                  }
                  
                  stack.push(temp);
                  stack.push(new TreeNode(-101));
  
              }else{
  
                  result.add(stack.pop().val);
  
              }
  
          }
  
          return result;
  
      }
  }
  

94. 二叉树的中序遍历

• 二叉树

  /**
   * Definition for a binary tree node.
   * 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;
   *     }
   * }
   */
  class Solution {
      public List<Integer> inorderTraversal(TreeNode root) {
  
          if(root==null){
              return new ArrayList<Integer>();
          }
  
          List<Integer> result=new ArrayList<>();
          Deque<TreeNode> stack=new ArrayDeque<>();
  
          stack.push(root);
  
          while(stack.size()!=0){
  
              TreeNode temp=stack.pop();
  
              if(temp.val!=-101){
  
                  if(temp.right!=null){
                      stack.push(temp.right);
                  }
  
                  stack.push(temp);
                  stack.push(new TreeNode(-101));
  
                  if(temp.left!=null){
                      stack.push(temp.left);
                  }
  
              }else{
  
                  result.add(stack.pop().val);
  
              }
  
          }
  
          return result;
  
      }
  }
  

145. 二叉树的后序遍历

• 二叉树

  /**
   * Definition for a binary tree node.
   * 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;
   *     }
   * }
   */
  class Solution {
      public List<Integer> postorderTraversal(TreeNode root) {
  
          if(root==null){
              return new ArrayList<Integer>();
          }
  
          List<Integer> result=new ArrayList<>();
          Deque<TreeNode> stack=new ArrayDeque<>();
  
          stack.push(root);
  
          while(stack.size()!=0){
  
              TreeNode temp=stack.pop();
  
              if(temp.val!=-101){
  
                  stack.push(temp);
                  stack.push(new TreeNode(-101));
  
                  if(temp.right!=null){
                      stack.push(temp.right);
                  }
  
                  if(temp.left!=null){
                      stack.push(temp.left);
                  }
  
              }else{
  
                  result.add(stack.pop().val);
  
              }
  
          }
  
          return result;
  
      }
  }