青岛网站设计选哪家,猪八戒网兼职接单,net快速建站,湖南人文科技学院招聘给定一个二叉树#xff0c;返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3
输出: [1,3,2] 进阶: 递归算法很简单#xff0c;你可以通过迭代算法完成吗#xff1f;
递归
/*** Definition for a binary tree node.* public class TreeNode …
给定一个二叉树返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3
输出: [1,3,2] 进阶: 递归算法很简单你可以通过迭代算法完成吗
递归
/*** 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 inorderTraversal(TreeNode root) {List Integer res new ArrayList ();helper(root, res);return res;}public void helper(TreeNode root, List Integer res) {if(root null)return;helper(root.left, res);res.add(root.val);helper(root.right, res);}
}
压栈
public class Solution {public List Integer inorderTraversal(TreeNode root) {List Integer res new ArrayList ();Stack TreeNode stack new Stack ();TreeNode curr root;while (curr ! null || !stack.isEmpty()) {while (curr ! null) {stack.push(curr);curr curr.left;}curr stack.pop();res.add(curr.val);curr curr.right;}return res;}
}
morris
虽然是空间O(1),但是oj并没有测出来效果依旧空间只超过40%
/*** 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 inorderTraversal(TreeNode root) {List Integer res new ArrayList ();TreeNode curr root;TreeNode pre;while (curr ! null) {if (curr.left null) {res.add(curr.val);curr curr.right; // move to next right node} else { // has a left subtreepre curr.left;while (pre.right ! null) { // find rightmostpre pre.right;}pre.right curr; // put cur after the pre nodeTreeNode temp curr; // store cur nodecurr curr.left; // move cur to the top of the new treetemp.left null; // original cur left be null, avoid infinite loops}}return res;}
}
