二叉树的前序遍历

╰+攻爆jí腚メ 2021-05-20 09:33 463阅读 0赞

````
//给定一个二叉树，返回它的 前序 遍历。  
//  
// 示例:  
// 输入: [1,null,2,3]  
// 1  
//  
// 2  
// /  
// 3  
//  
//输出: [1,2,3]  
//  
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？  
// Related Topics 栈 树
````
````
    import java.util.ArrayList;
    import java.util.Stack;
    
    /** * 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> nodeList = new ArrayList<>(); //遍历结果
    		// 空树判断
    		if (root == null) return nodeList;
    		// 模拟递归的栈
    		Stack<TreeNode> stack = new Stack<>();
    		// 先压入根节点
    		stack.push(root);
    		while(!stack.empty()) { 
    			// 出栈，遍历根节点
    			TreeNode treeNode = stack.pop();
    			nodeList.add(treeNode.val);
    			// 前序遍历是 根-左-右；压栈顺序应是 先压右子树，右子树是后面访问的
    			if (treeNode.right != null) { 
    				stack.push(treeNode.right);
    			}
    			if (treeNode.left != null) { 
    				stack.push(treeNode.left);
    			}
    		}
    		return nodeList;
    	}
    }
    ···
    ```java
    import java.util.ArrayList;
    import java.util.Stack;
    
    /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
    	List<Integer> res = new ArrayList<>();
    	public List<Integer> preorderTraversal(TreeNode root) { 
    		if(root==null) return res;
    		res.add(root.val);
    		preorderTraversal(root.left);
    		preorderTraversal(root.right);
    		return res;
    	}
    }
````