LeetCode : Binary Tree Preorder Traversal 二叉树前序遍历递归迭代

桃扇骨 2021-06-24 16:10 376阅读 0赞

**试题：**  
Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: \[1,null,2,3\]  
1  
  
2  
/  
3

Output: \[1,2,3\]  
Follow up: Recursive solution is trivial, could you do it iteratively?  
**代码：**  
递归：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        List<Integer> out = new ArrayList<Integer>();
        public List<Integer> preorderTraversal(TreeNode root) {
            if(root==null) return out;
            out.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
            return out;
        }
    }

迭代：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> out = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode tmp = stack.pop();
                if(tmp==null) continue;
                out.add(tmp.val);
                stack.push(tmp.right);
                stack.push(tmp.left);
            }
            return out;
        }
    }