二叉树先序遍历的两种思路

二叉树先序遍历的两种思路

遍历思路

• 遍历二叉树
• 首先判断一个节点应该做什么
• 然后遍历左子树 遍历右子树

/*** 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 {List<Integer> res = new LinkedList<>();public List<Integer> preorderTraversal(TreeNode root) {traverse(root);return res;}void traverse(TreeNode root){if(root == null){return;}// 先序遍历res.add(root.val);traverse(root.left);traverse(root.right);}
}

分解思路

• 二叉树的先序遍历结果 = 根节点+ 左子树的先序遍历结果 + 右子树的先序遍历结果

/*** 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) {List<Integer> res = new LinkedList<>();if(root == null){return res;}// 检查一个节点要做的事情res.add(root.val);// 利用函数定义  后面接着左子树的先序遍历结果res.addAll(preorderTraversal(root.left));res.addAll(preorderTraversal(root.right));return res;}
}