94. 二叉树的中序遍历:

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

样例 1:

算法leetcode|94. 二叉树的中序遍历(多语言实现)-LMLPHP

输入:
	
	root = [1,null,2,3]
	
输出:
	
	[1,3,2]

样例 2:

输入:
	
	root = []
	
输出:
	
	[]

样例 3:

输入:
	
	root = [1]
	
输出:
	
	[1]

提示:

  • 树中节点数目在范围 [0, 100]
  • -100 <= Node.val <= 100

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 二叉树的中序遍历和前序遍历,后续遍历是二叉树常用的遍历方式。
  • 使用递归方式比循环非递归方式更加简单,直观,易于理解。
  • 通常二叉树的中序遍历一定要使用一个栈结构,因为中序遍历的要求是遍历完左子树才能遍历当前节点,但是遍历到了左子树就无法再回到当前节点了,所以一般都是使用压栈的方式,先将当前节点压栈,遍历完左子树再将当前节点出栈,这样空间复杂度就会是 O(n) (递归也相当于使用了栈结构)。
  • 说起来这不是什么大问题,但是算法就是要想办法优化降低时间和空间的复杂度,于是寄出一种可以将空间复杂度降低为 O(1) 的中序遍历方式,Morris 中序遍历。
  • 事实上Morris 中序遍历不是没有代价的,由于要做额外的节点连接和恢复,相当于用时间换空间。

题解:

rust:

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(mut root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = Vec::new();

        while root != None {
            if root.as_ref().unwrap().borrow().left != None {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                let mut predecessor = root.as_ref().unwrap().borrow().left.clone();
                while predecessor.as_ref().unwrap().borrow().right != None
                    && predecessor.as_ref().unwrap().borrow().right != root {
                    predecessor = predecessor.unwrap().borrow().right.clone();
                }

                if predecessor.as_ref().unwrap().borrow().right == None {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.unwrap().borrow_mut().right = root.clone();
                    // 遍历左子树
                    root = root.unwrap().borrow().left.clone();
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.unwrap().borrow_mut().right = None;
                }
            }
            // 遍历当前 root 节点
            ans.push(root.as_ref().unwrap().borrow().val);
            // 遍历当前 root 节点的右子树
            root = root.unwrap().borrow().right.clone();
        }

        return ans;
    }
}

go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var ans []int

	for root != nil {
		if root.Left != nil {
			// 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
			predecessor := root.Left
			for predecessor.Right != nil && predecessor.Right != root {
				// 有右子树且没有设置过指向 root,则继续向右走
				predecessor = predecessor.Right
			}

			if predecessor.Right == nil {
				// 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
				predecessor.Right = root
				// 遍历左子树
				root = root.Left
				continue
			} else {
				// 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
				predecessor.Right = nil
			}
		}
		// 遍历当前 root 节点
		ans = append(ans, root.Val)
		// 遍历当前 root 节点的右子树
		root = root.Right
	}

	return ans
}

c++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                TreeNode *predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }

                if (predecessor->right == nullptr) {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor->right = root;
                    // 遍历左子树
                    root = root->left;
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor->right = nullptr;
                }
            }
            // 遍历当前 root 节点
            ans.emplace_back(root->val);
            // 遍历当前 root 节点的右子树
            root = root->right;
        }

        return ans;
    }
};

python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()

        while root is not None:
            if root.left is not None:
                # 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                predecessor = root.left
                while predecessor.right is not None and predecessor.right != root:
                    # 有右子树且没有设置过指向 root,则继续向右走
                    predecessor = predecessor.right

                if predecessor.right is None:
                    # 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.right = root
                    # 遍历左子树
                    root = root.left
                    continue
                else:
                    # 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.right = None
            # 遍历当前 root 节点
            ans.append(root.val)
            # 遍历当前 root 节点的右子树
            root = root.right

        return ans


java:

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();

        while (root != null) {
            if (root.left != null) {
                // 寻找当前 root 节点的前驱节点:前驱 predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
                TreeNode predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // 让前驱 predecessor 节点的右指针指向当前 root 节点,继续遍历左子树,之后会再次回到当前 root 节点
                    predecessor.right = root;
                    // 遍历左子树
                    root = root.left;
                    continue;
                } else {
                    // 左子树遍历完毕又回到了当前 root 节点,让前驱 predecessor 节点的右指针与当前 root 节点断开,恢复原样
                    predecessor.right = null;
                }
            }
            // 遍历当前 root 节点
            ans.add(root.val);
            // 遍历当前 root 节点的右子树
            root = root.right;
        }

        return ans;
    }
}


12-26 07:08