讨论/《零起步学算法》 - 例题:二叉树的前序遍历/
《零起步学算法》 - 例题:二叉树的前序遍历
共 1 个回复

借助双端队列实现二叉树的前根遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
      //深度优先遍历 => 深度遍历
      List<Integer> res = new LinkedList<>();
      //判空
      if(root == null) {
        return res;
      }
      //双端队列=> 栈
      Deque<TreeNode> stack = new LinkedList<>();
      //添加根结点
      stack.addFirst(root);
      //循环遍历
      while(!stack.isEmpty()) {
        //先根遍历 先根,后左,最后右 
        //出栈
        TreeNode head = stack.removeFirst();
        res.add(head.val);
        if(head.right != null) {
          stack.addFirst(head.right);
        }
        if(head.left != null) {
          stack.addFirst(head.left);
        }
      }
      return res;
    }
}
1