从零学算法94
2023-12-26 17:35:00
94.给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
-
树的中序遍历是是访问树的
左节点 -> 根节点 -> 右节点
这样的顺序,同时,对于每个左节点和右节点,也是遵从同样的访问顺序,你会发现这就是天然的递归,递归的最小基本单元就是{处理左节点;处理根节点;处理右节点}
-
class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs(TreeNode root){ // 如果遍历到 null 就往上返回 if(root == null)return; // 我们要先得到最左节点,所以先处理左节点 // 处理方式就是一直按照左根右的顺序遍历 dfs(root.left); // 到最左节点后再执行 dfs(root.left) 就会被 return // 继续执行,此时的 root 就是最左节点,所以添加到 list // 并且其实看下图,对于最左节点 2 来说,它也是一棵树的根节点 // 也就是说我们这里就是符合 list.add(root.val); // 右节点也是同样的处理方式,让他左根右不断遍历访问 dfs(root.right); } } 1 1 / \ / \ 2 3 2 3 / \ / \ null 4 null null
-
上面的递归隐式地维护了一个栈,我们用迭代的方式显式地表示一遍。
-
首先是
dfs(root.left)
,它的作用是不断往左边找节点,找到最左的,找到后往上回溯的时候,是先处理最近递归到的,这就是栈的先进先出的特点,所以它就等价于不断把左节点入栈 -
然后是左节点遍历到 null 后往上回溯到最左节点,然后
list.add(root.val);
,回溯到最左节点,其实不就是弹出栈顶元素 node,然后也是把值添加到 list -
最后是
dfs(root.right);
,就是要用同样的方式处理右节点去了,我们就把用来遍历的 root,更新到 node.right 然后继续按照同样的方式处理 -
public List<Integer> inorderTraversal(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { // 不断把左节点入栈 while (root != null) { stack.push(root); root = root.left; } if (!stack.isEmpty()) { // 最左节点出栈取值 TreeNode node = stack.pop(); list.add(node.val); root = node.right; } } return list; }
文章来源:https://blog.csdn.net/m0_53256503/article/details/135145465
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!