医药网站开发,网站客户留言,网上购物商城建设,网站开发培训心得文章目录 二叉树递归遍历解题思路代码总结 二叉树的迭代遍历解题思路代码总结 二叉树的统一迭代法解题思路代码总结 草稿图网站 java的Deque
二叉树递归遍历 题目#xff1a; 144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历 解析#xff1a;代码随想录解析… 文章目录 二叉树递归遍历解题思路代码总结 二叉树的迭代遍历解题思路代码总结 二叉树的统一迭代法解题思路代码总结 草稿图网站 java的Deque
二叉树递归遍历 题目 144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历 解析代码随想录解析 解题思路
递归遍历 前序NLR 中序LNR 后序LRN
代码
/*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();preorder(root, res);return res;}public void preorder(TreeNode root, ListInteger res){if (root null)return;res.add(root.val);preorder(root.left, res);preorder(root.right, res);}
}//中序
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();inorder(root, res);return res;}public void inorder(TreeNode root, ListInteger res){if (root null)return;inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}
//后序
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();postorder(root, res);return res;}public void postorder(TreeNode root, ListInteger res){if (root null)return;postorder(root.left, res);postorder(root.right, res);res.add(root.val);}
}总结
暂无
二叉树的迭代遍历 题目 144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历 解析代码随想录解析 解题思路
前序利用一个栈每次出栈并入栈。 中序利用一个栈cur指向root节点一直走左子树并入栈到空cur为空时输出栈顶的val然后使cur指向出栈节点右子树重复上述步骤。 后序LRN反过来是NRL也就是前序换一下最后倒转一下。
代码
/*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode tmp stack.pop();res.add(tmp.val);if (tmp.right ! null)stack.push(tmp.right);if (tmp.left ! null)stack.push(tmp.left);}return res;}
}//中序
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();TreeNode cur root;while (!stack.isEmpty() || cur ! null){if (cur ! null){stack.push(cur);cur cur.left;}else{cur stack.pop();res.add(cur.val);cur cur.right;}}return res;}
}//后序
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode tmp stack.pop();res.add(tmp.val);if (tmp.left ! null)stack.push(tmp.left);if (tmp.right ! null)stack.push(tmp.right);}Collections.reverse(res);return res;}
}总结
死去的408记忆在攻击我
二叉树的统一迭代法 题目 144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历 解析代码随想录解析 解题思路
代码结构和递归遍历相似。下面是模拟步骤图 前序
中序
后序
代码
/*** 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 ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if (node ! null){stack.pop();if (node.right ! null) stack.push(node.right);if (node.left ! null) stack.push(node.left);stack.push(node);stack.push(null); }else{stack.pop();node stack.pop();res.add(node.val);}}return res;}
}//中序
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if (node ! null){stack.pop();if (node.right ! null) stack.push(node.right);stack.push(node);stack.push(null); if (node.left ! null) stack.push(node.left);}else{stack.pop();node stack.pop();res.add(node.val);}}return res;}
}//后序
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null)return res;StackTreeNode stack new StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode node stack.peek();if (node ! null){stack.pop();stack.push(node);stack.push(null); if (node.right ! null) stack.push(node.right);if (node.left ! null) stack.push(node.left);}else{stack.pop();node stack.pop();res.add(node.val);}}return res;}
}总结
感觉记住了感觉。
