广告网站怎么设计制作,edm营销网站,关键词优化工具,海口网站建设做网站题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 解题思路#xff1a;
方法一#xff1a;递归
中序遍历的操作定义为#xff0c;若二叉树为空#xff0c;则空操作#xff0c;否则#xff1a;
中序遍历左子树访问根节点中…题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 解题思路
方法一递归
中序遍历的操作定义为若二叉树为空则空操作否则
中序遍历左子树访问根节点中序遍历右子树
AC代码
/*** 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 inorderTraversal(TreeNode root) {ListInteger result new ArrayList();process(result,root);return result;}public void process(ListInteger result ,TreeNode root){if (rootnull){return;}//中序遍历左子树process(result,root.left);//访问根节点result.add(root.val);//中序遍历右子树process(result,root.right);}
} 方法二迭代递归的循环版本借助栈来完成递归
如果root !null 或者 stack的大小不为0则循环执行
如果root !null循环将节点和其左孩子入栈执行 stack.push(root)将root入栈rootroot.left继续将root的左孩子入栈上面循环结束后栈顶节点没有左孩子此时可以访问该节点 root stack.pop()result.add(root.val)该节点没有左孩子可以访问该节点令root root.right对该节点的右孩子继续执行上述操作如果其右孩子有左孩子将左孩子入栈
/*** 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 inorderTraversal(TreeNode root) {ListInteger result new ArrayList();DequeTreeNode stack new LinkedList();while (root!null||!stack.isEmpty()){//遍历左子树while (root!null){stack.push(root);rootroot.left;}root stack.pop();//访问根节点result.add(root.val);//遍历右子树rootroot.right;}return result;}
}
