赞
踩
思路1:使用递归的方式中序遍历
中序中的访问元素顺序
思想 ——> 利用栈,入栈采用 右 中 左的顺序,此时弹出就是 左 中 右
根节点5
——> 4
——> 1
,利用 **栈 **记录遍历的顺序1
的左叶子结点,发现 1
的左孩子 null
了,此时从栈取元素,弹出 1
1
的右叶子结点,发现 1
的右孩子 null
了,此时从栈取元素,弹出 4
4
的右孩子,此时 4
的右孩子不为 null
,此时 入栈 2
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
// 递归 终止条件
if(root==null){
return res;
}
// 递归逻辑
inorderTraversal(root.left);
res.add(root.val);
inorderTraversal(root.right);
return res;
}
}
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null){ return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if (cur != null){ stack.push(cur); cur = cur.left; }else{ cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
public class inOrder { static class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int x){ val = x; } } public static TreeNode build(Integer[] nums){ //借助 队列实现 TreeNode root = new TreeNode(nums[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int index = 1; while(!queue.isEmpty()){ TreeNode newNode = queue.poll(); if(index<nums.length && nums[index]!=null){ root.left = new TreeNode(nums[index]); queue.offer(root.left); } index++; if(index<nums.length && nums[index]!=null){ root.right = new TreeNode(nums[index]); queue.offer(root.right); } index++; } return root; } // 中序 static List<Integer> res = new ArrayList<>(); public static List<Integer> inOrderT(TreeNode root){ // 判空 if(root==null){ return res; } TreeNode cur = root; Stack<TreeNode> st = new Stack<>(); while(cur!=null || !st.isEmpty()){ if(cur!=null){ st.push(cur); cur = cur.left; }else{ cur = st.pop(); res.add(cur.val); cur = cur.right; } } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入二叉树构造序列"); String input = sc.next(); input = input.replace("[",""); input = input.replace("]",""); String[] part = input.split(","); Integer[] nums = new Integer[part.length]; for(int i = 0 ; i < part.length;i++){ if(!part[i].equals("null")){ nums[i] = Integer.parseInt(part[i]); }else{ nums[i] = null; } } TreeNode root = build(nums); List<Integer> forRes = inOrderT(root); System.out.println(forRes.toString()); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。