上海学做网站,十大设计创意产品网站,织梦模板是什么,湖南常德二叉树的遍历 递归法前序遍历中序遍历后序遍历改进 迭代法前序、后序遍历中序遍历 二叉树的统一迭代法(未完成)Java 中 null、NULL、nullptr 区别 public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(in… 二叉树的遍历 递归法前序遍历中序遍历后序遍历改进 迭代法前序、后序遍历中序遍历 二叉树的统一迭代法(未完成)Java 中 null、NULL、nullptr 区别 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;}
}递归法
前序、中序、后序怎么区分 前、中、后其实描述的是根节点一颗树有左子树、根节点、右子树的访问时间。 前序遍历根节点-左子树-右子树。 中序遍历左子树-根节点-右子树。 后序遍历左子树-右子树-根节点。 LeetCode题目144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历。 前序遍历
class Solution {ListInteger mylist new ArrayListInteger();public ListInteger preorderTraversal(TreeNode root) {if(root null) return mylist;mylist.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return mylist;}
}中序遍历
class Solution {ListInteger mylist new ArrayListInteger();public ListInteger inorderTraversal(TreeNode root) {if(root null) return mylist;inorderTraversal(root.left);mylist.add(root.val);inorderTraversal(root.right);return mylist;}
}后序遍历
class Solution {ListInteger mylist new ArrayListInteger();public ListInteger postorderTraversal(TreeNode root) {if(root null) return mylist;postorderTraversal(root.left);postorderTraversal(root.right);mylist.add(root.val);return mylist;}
}改进
以前序遍历为例以下是代码随想录的代码。
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayListInteger();preorder(root, result);return result;}public void preorder(TreeNode root, ListInteger result) {if (root null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}迭代法 以下是笔记from 代码随想录 编程语言实现递归的逻辑是用栈这种数据结构实现的。
前序、后序遍历
注意栈操作中判断是否为空的方法有两个isEmpty 和 empty 都可以。
前序 前序遍历是 根左右所以压入栈的顺序应该是右、左
class Solution {public ListInteger preorderTraversal(TreeNode root) {StackTreeNode s new Stack();ListInteger ans new ArrayListInteger();if(root null) return ans;else s.push(root);while(!s.isEmpty()) {TreeNode tmp s.pop();ans.add(tmp.val);if(tmp.right ! null) s.push(tmp.right);if(tmp.left ! null) s.push(tmp.left);}return ans;}
}后序 前序遍历顺序是 根左右后续是左右根只需要把上文中的前序遍历的顺序变成 根右左然后反转结果数组/list就可以。 反转的方法 Collections.reverse(ans);
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger ans new ArrayList();if(root null) return ans;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()) {TreeNode tmp stack.pop();ans.add(tmp.val);if(tmp.left ! null) stack.push(tmp.left);if(tmp.right ! null) stack.push(tmp.right);}Collections.reverse(ans);return ans;}
}中序遍历
中序遍历的访问顺序和处理顺序是不一样的。一棵树是从根节点开始访问的。前序遍历的根左右顺序保证了访问顺序和处理顺序相同。 但是中序遍历的顺序是左根右。 分析 中序遍历的顺序是左根右处理完所有的左子树、再处理根节点、最后处理所有的右子树。 因为代码中是用根节点root定位一棵树的遍历树的时候从根节点开始但是中序遍历处理处理的意思在这里就是把节点的值加入到数组中不是先处理根节点。 所以用栈先存下所有的左子树处理完根节点之后再处理左子树。
class Solution { public ListInteger inorderTraversal(TreeNode root) {ListInteger ans new ArrayList();if(root null) return ans;StackTreeNode mystack new Stack();TreeNode cur root;while(cur ! null || !mystack.isEmpty()) {if(cur ! null) {mystack.push(cur);cur cur.left;} else {cur mystack.pop();ans.add(cur.val);cur cur.right;}}return ans;}
}二叉树的统一迭代法(未完成)
Java 中 null、NULL、nullptr 区别
1NULL 不是 Java 中的关键字 2nullptr 不是 Java 中的关键字
3在 Java 中null 表示“没有值”或“空”。它是一个关键字用于表示一个对象变量不引用任何对象。这意味着该变量没有指向任何有效的内存地址
