94. 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

• 递归

  public List<Integer> inorderTraversal(TreeNode root) {
      if(root == null) return  new ArrayList<Integer>();
      List<Integer> ans = new ArrayList<>();
  
      if(root.left==null&&root.right==null){
          ans.add(root.val);
          return ans;
      }
  
      List<Integer> LEFT = inorderTraversal(root.left);
      List<Integer> RIGHT = inorderTraversal(root.right);
      if(LEFT!=null){
          for(int e:LEFT){
              ans.add(e);
          }
      }
  
      ans.add(root.val);
      if(RIGHT!=null){
          for(int e:RIGHT){
              ans.add(e);
          }
      }
  
      return ans;
  
  }
  

• 栈

  public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Stack<TreeNode> stack = new Stack<>();
      while(root!=null||!stack.isEmpty()){
          while(root!=null){
              stack.push(root);
              root = root.left;
          }
          root = stack.pop();
          res.add(root.val);
          root = root.right;
      }
      return res;
  }